Vertex adjacencies in the set covering polyhedron

Néstor E. Aguilera, Ricardo D. Katz, Paola B. TolomeiDiscret. Appl. Math 2017 · OpenReview

TL;DR

This paper tackles the problem of understanding how vertices are connected (adjacent) in the set covering polyhedron, a fundamental structure in optimization. The authors introduce a new graph-theoretic condition for adjacency and fully characterize it for a special class of matrices called "row circular" matrices, paving the way for more efficient algorithms and new insights into related combinatorial problems.

What Problem Does This Paper Address?

The set covering problem is a classic optimization challenge: given a universe of elements and a collection of sets, find the smallest subcollection of sets whose union covers all elements. The "set covering polyhedron" is a geometric object that captures all possible solutions to this problem. Understanding the "adjacency" of its vertices – how they are connected by edges – is crucial for developing algorithms that solve the set covering problem and for understanding related combinatorial structures. While a characterization of vertex adjacency exists for the related "stable set polytope" (based on graph connectivity), a similar simple characterization for the set covering polyhedron has remained elusive due to its complexity. This paper aims to bridge this gap by providing a new sufficient condition for adjacency and a complete characterization for a specific, yet important, class of matrices.

Methods

The core of the paper lies in introducing and analyzing a novel graph called the "joint saturation graph" (G(v, v')). This graph is constructed for any pair of vertices (v, v') of the set covering polyhedron. The edges of this graph represent relationships between elements that are "saturated" (i.e., exactly covered) by both vertices. The authors then prove that if this joint saturation graph is "partite-connected" (a specific structural property), then the corresponding vertices are adjacent.

A significant portion of the paper is dedicated to analyzing this condition for "row circular matrices." These matrices have a special structure where each row's non-zero entries form a "circular arc" on the indices. For this class of matrices, the authors provide a complete characterization of vertex adjacency, showing that it is equivalent to the joint saturation graph being either connected or "almost-connected" (a slightly weaker condition) with specific properties regarding the overlap of vertex supports.

Datasets

Not discussed in the paper. The paper focuses on theoretical properties of polyhedra defined by binary matrices, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • The Joint Saturation Graph: This is the central new concept. It provides a powerful graph-theoretic tool to analyze vertex relationships in the set covering polyhedron, moving beyond simple connectivity.
  • Partite-Connectivity as a Sufficient Condition: The paper establishes that a specific structural property of the joint saturation graph (partite-connectivity) is sufficient for vertex adjacency. This is a significant step towards understanding adjacency.
  • Full Characterization for Row Circular Matrices: The most impactful result is the complete characterization of adjacency for row circular matrices. This means for this important class of problems, we now know precisely when two vertices are adjacent based on the structure of their joint saturation graph.
  • Connection to Minimally Nonideal Matrices: The authors demonstrate how their findings can be used to construct new infinite families of "minimally nonideal" matrices, which are important in polyhedral combinatorics.

Key Results

  • Theorem 4.3: If the joint saturation graph of two distinct vertices of Q(A) is partite-connected, then these vertices are adjacent in Q(A).
  • Theorem 5.14: For a row circular matrix A, two distinct vertices v and v' of Q*(A) are adjacent if and only if their joint saturation graph G(v, v') is either connected, or almost-connected with disjoint supports.
  • The paper also provides a method to construct new infinite families of minimally nonideal matrices based on existing ones.

Limitations and Future Work

The paper acknowledges that the sufficient condition for adjacency (partite-connectivity of the joint saturation graph) is not always necessary, except for the case of row circular matrices where a full characterization is provided. The authors suggest that further work could explore extending these characterizations to broader classes of matrices. Additionally, the paper hints at the potential for these results to lead to more efficient algorithms for solving set covering problems, which would be a natural direction for future research.

Summary updated

Abstract

We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by Chvátal for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices.
BibTeX
@inproceedings{aguilera2017vertex,
  author = {Néstor E. Aguilera and Ricardo D. Katz and Paola B. Tolomei},
  title = {{Vertex adjacencies in the set covering polyhedron}},
  booktitle = {Discret. Appl. Math},
  year = {2017},
  url = {https://openreview.net/forum?id=4GYYbPa2hd},
}

Loading related content...

Figure