Universidade Federal do Ceará
Mestrado e Doutorado em Ciências da Computação

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, respectively. A signed graph is balanced if its vertex set can be partitioned into U and Ū in such a way that every negative edge has one end in U and the other one in Ū, 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 Ū. 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 familly 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-inducing 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, 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 BSS problem.

• Prof. Dr. Manoel Bezerra Campêlo Neto (MDCC/UFC) – Orientador
• Prof. Dr. Victor Almeida Campos (MDCC/UFC)
• Prof. Dr. Márcio Costa Santos (UFMG)
• Prof. Dr. Phablo Fernando Soares Moura (KU Leuven)