O Seminário de Combinatória continua as suas atividades de forma online e encerra o ano de 2024 com chave de ouro.
Agradecemos a oportunidade de receber o professor Uéverton Souza da Universidade Federal Fluminense e membro afiliado da Academia Brasileira de Ciências.
Data: 11/12/2024
Horário: 14:00h (Brasil)
Sala: https://meet.google.com/cde-osms-aqn
Palestrante: Ueverton Souza, Universidade Federal Fluminense
Título: Realizing Graphs with Cut Constraints
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 (repre-
senting 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.
Este é um trabalho em conjunto com Vítor Chagas, Samuel de Paula, Greis Quesquén e Lucas de Oliveira.
Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem, e e-mail no Chat ao final do seminário.
Não é necessária inscrição prévia. Agradecemos a ajuda na divulgação encaminhando esta mensagem.
Para se inscrever na lista:
https://groups.google.com/d/forum/seminarios-combinatoria-uff