Affordable Access

Publisher Website

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
  • Polyhedral Combinatorics
  • Dominating Set Problem
  • Set Covering Problem
  • Circulant Matrices
  • Web Graphs
Disciplines
  • Computer Science

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.