Data: 11/12/2024

Título: Realizing Graphs with Cut Constraints.

Palestrante: Ueverton Souza, Universidade Federal Fluminense.

Data: 11 de dezembro de 2024, 14 h (Brasil).

Resumo: Given a finite non-decreasing sequence d = (d1, . . . , dn) of natural numbers, the Graph Realization problem asks whether d is a graphic sequence, i.e., there exists a labeled simple graph such that (d1, . . . , dn) is the degree sequence of this graph. Such a problem can be solved in polynomial time due to the Erdős and Gallai characterization of graphic sequences. Since vertex degree is the size of a trivial edge cut, we consider a natural generalization of Graph Realization, where we are given a finite sequence d = (d1, . . . , dn) of natural numbers (representing the trivial edge cut sizes) and a list of nontrivial cut constraints L composed of pairs (Sj , ℓj ) where Sj ⊂ {v1, . . . , vn}, and ℓj is a natural number. In such a problem, we are asked whether there is a simple graph with vertex set V = {v1, . . . , vn} such that vi has degree di and ∂(Sj ) is an edge cut of size ℓj , for each (Sj , ℓj ) ∈ L. We show that such a problem is polynomial-time solvable whenever each Sj has size at most three. Conversely, assuming P ≠ NP, we prove that it cannot be solved in polynomial time when L contains pairs with sets of size four, and our hardness result holds even assuming that each di of d equals 1. 

Nota: Este é um trabalho em conjunto com Vítor Chagas, Samuel de Paula, Greis Quesquén e Lucas de Oliveira. 

Obs: Vídeo