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

Título: Revisiting the Balanced Induced Subgraph Polytope

Data: 08/11/2024
Horário: 15h
Local: Sala de Reuniões do Bloco 910

Resumo:

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 in two disjoint sets S and S, that correspond to the negative and positive edges of G, respectively. Multiple edges and loops are allowed. A signed graph is balanced if the vertex set V can be partitioned in U and U in such a way that all negative edges have one endpoint in U and the other one in U¯, and all positive edges have both endpoints 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) 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 PG, consists of the convex hull of its balanced induced subgraphs’ vertex-incidence vectors. Using an affine transformation from PG to a set covering polytope, we investigate relations between facets from one polytope to the other.

Banca examinadora:

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