# The set covering problem on circulant matrices: polynomial instances and the relation with the dominating set problem on webs

- Authors
- Journal
- Electronic Notes in Discrete Mathematics 1571-0653
- Publisher
- Elsevier
- Publication Date
- Volume
- 36
- Identifiers
- DOI: 10.1016/j.endm.2010.05.150
- Keywords
- Disciplines

## Abstract

Abstract The dominating set polyhedron of a web graph W n k is the set covering polyhedron of a circulant matrix C n 2 k + 1 . In a previous work we generalize the results by Argiroffo and Bianchi on valid inequalities associated with every circulant minor of a circulant matrix and we conjecture that, for any k, the minor inequalities together with the boolean facets and the rank constraint are enough to describe the set covering polyhedron of C n k . In this work we prove that the conjecture is true for the family of C s k + r k with s = 2 , 3 and 0 ⩽ r ⩽ s − 1 and give a polynomial separation algorithm for inequalities involved in the description. Thus, we prove the polynomiality of the set covering problem on these families. As a consequence we obtain the polynomiality of the minimum weight dominating set problem on webs of the form W n t , when n = 2 s t + s + r with s = 2 , 3 and 0 ⩽ r ⩽ s − 1 .

## There are no comments yet on this publication. Be the first to share your thoughts.