Revisiting the Balanced Induced Subgraph Polytope: a polyhedral study via clutters

Abstract

A signed graph G is a graph associated with a sign function, which maps each edge of G to a positive or negative sign. Thus, the edge set E of G can be partitioned into two disjoint sets that correspond to the negative and positive edges of G. A signed graph is balanced if its vertex set can be partitioned into U and U in such a way that every negative edge has one end in U and the other one in U, and every positive edge has both ends in the same partition, that is, there is no positive edge in the cut defined by U and U. The Balanced Induced Subgraph problem (BIS) is an NP-hard problem that consists in, given a signed graph G with a weight associated to each vertex, finding a balanced induced subgraph of G that maximizes the sum of weights of its vertices. The balanced induced subgraph polytope of G, namely P(G), consists of the convex hull of its balanced induced subgraphs’ vertex-incidence vectors. Using an affine transformation from P(G) to a set covering polytope, this study investigates relations between facets from one polytope to the other. As a set covering problem, BIS is studied from the point of view of clutters. Clutters are collections of minimal subsets of a set, and they have a strong relation with covering problems. Several results contained in this work, such as facet-defining inequalities and lifting procedures, are valid to any family of clutters, so they can be readily extended to other set covering problems. This work also extends the study of N-set inequalities, which are a generalization of rank inequalities, and establishes relations between facet-defining substructures of a signed graph and minors of the clutter related to the BIS polytope. The edge-version of BIS, namely the Balanced Spanning Subgraph problem (BSS), is also considered. It is shown that the BSS polytopes are a subclass of BIS polytopes. This result also shows how to obtain an instance of the BIS problem equivalent to an instance of the Balanced Spanning Subgraph problem.