In this paper we present an extended formulation for the dominating set polytope via facility location. We show that with this formulation we may describe the dominating set polytope for some class of graphs as cacti graphs, though its description in the natural node variables dimension has been only partially obtained. Moreover, the inequalities describing this polytope have coefficients in {−1, 0, 1}. This is not the case for the dominating set polytope in the node-variables dimension. It is known from [9] that for any integer p, there exists a facet defining inequality having coefficients in {1, . . . , p}. We also show a decomposition theorem by means of 1-sums. Again this decomposition is much simpler with the extended formulation than with the node-variables formulation given in [10]. We also give a linear time algorithm to solve the minimum dominating set problem in cacti graphs.
By: Mourad Baïou, Francisco Barahona
Published in: RC25325 in 2012
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .