The Dominating Set Polytope via Facility Location

In this paper we present an extended formulation for the dominating set polytope via facility location. We show that with this formulation we can describe the dominating set polytope for 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 [1] 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 [2].

By: Mourad Baïou, Francisco Barahona

Published in: RC25455 in 2014


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 .