Defesa de Tese de Doutorado de Gabriel Lagoa Duarte – 08/04/2025, 14h, sala 310 do Instituto de Computação
Co-treewidth, Co-degeneracy e os Fechos de Bondy e Chvátal
Resumo:
Para problemas que são tratáveis quando parametrizados pela treewidth e intratáveis quando parametrizados pela clique-width, pode haver infinitas famílias de instâncias com clique-width limitada e treewidth não limitada onde o problema pode ser solucionado eficientemente. Longest Cycle, Longest Path, Path Cover, Cycle Cover, Max-Cut, Edge Dominating Set, e Graph Coloring são exemplos de problemas que são FPT quando parametrizados pela treewidth e que não podem ser resolvidos em tempo FPT quando parametrizados pela clique-width, assumindo FPT != W[1]. Em 2017, Knop, Koutecký, Masařík, e Toufar [WG 2017] perguntaram sobre a complexidade de problemas de decisão Π sobre o grafo complementar de G considerando um parâmetro p de G, especialmente para parâmetros esparsos como a treewidth. A treewidth de um grafo complementar, proposto ser chamado de co-treewidth, parece ser um bom parâmetro de largura para lidar com instâncias densas de problemas que são consideradas “difíceis” em respeito a clique-width. Nesse trabalho, nós iniciamos um estudo sistemático sobre a parametrização pela co-treewidth. Além disso, como a degeneração de um grafo é, no máximo, sua treewidth, introduzimos um estudo sobre a co-degeneracy (a degeneração do grafo complementar) como um parâmetro.
Em 1976, Bondy e Chvátal [DM 1976] introduziram as noções de fecho de um grafo e a estabilidade de propriedades em grafos. Nesse trabalho, desenvolvemos um framework algorítmico para a parametrização por co-degeneracy baseado na noção de fechos para resolver problemas que são (n + ℓ)-estáveis para algum ℓ limitado a uma função da co-degeneracy. Usando esse framework, é mostrado que Longest Path, Longest Cycle, e Path Cover são todos tratáveis por parâmetro fixo quando parametrizados pela co-degeneracy. Além disso, determinamos a estabilidade da propriedade de ter uma cobertura por ciclos de tamanho no máximo r. Após isso, usamos nosso framework, junto com alguns resultados e técnicas apresentadas em Jansen, Kozma, and Nederlof [WG 2019], mostramos que Cycle Cover parametrizado pela co-degeneracy admite um kernel linear sob o número de vértices. Fora isso, nós também mostramos que Edge Dominating Set é FPT quando parametrizado pela co-degeneracy. Por outro lado, reforçamos que Graph Coloring embora seja para-NP-completo quando parametrizado pela co-degeneracy é FPT quando parametrizado pela co-treewidth. Relativo a MaxCut, apresentamos um algoritmo FPT parametrizado pela co-treewidth, enquanto deixamos aberto sua complexidade quando parametrizado pela co-degeneracy. Adicionalmente, mostramos que Precoloring Extension é FPT quando parametrizado pela co-treewidth, enquanto esse problema é conhecido por ser W[1]-difícil quando parametrizado pela treewidth.
Abstract:
For problems that are fixed-parameter tractable when parameterized by treewidth, but intractable when parameterized by clique-width, there may exist infinite families of instances of bounded clique-width and unbounded treewidth where the problem can be solved efficiently. Longest Cycle, Longest Path, Path Cover, Cycle Cover, MaxCut, Edge Dominating Set, and Graph Coloring are examples of problems that are FPT when parameterized by treewidth but cannot be solved in FPT time when parameterized by clique-width assuming FPT != W[1]. In 2017, Knop, Koutecký, Masařík, and Toufar [WG 2017] asked about the complexity of deciding graph problems Π on the complement of G considering a parameter p of G, especially for sparse graph parameters such as treewidth. The treewidth of the complement of the input graph, proposed be called co-treewidth, seems a nice width parameter to deal with dense instances of problems that are “hard” concerning clique-width. In this work, we initiate a systematic study of co-treewidth parameterization. Also, since the degeneracy of a graph is at most its treewidth, we introduce the study of co-degeneracy (the degeneracy of the complement graph) as a parameter.
In 1976, Bondy and Chvátal [DM 1976] introduced the notions of graph closures and stability of graph properties. In this thesis, we develop an algorithmic framework for co-degeneracy parameterization based on the notion of closures for solving problems that are (n + ℓ)-stable for some ℓ bounded by a function of the co-degeneracy. Using such a framework, it is shown that Longest Path, Longest Cycle, and Path Cover are all fixed-parameter tractable when parameterized by co-degeneracy. In addition, we determine the stability of the property of having a cycle cover of size at most r. After that, using our closure framework together with some results and techniques presented in Jansen, Kozma, and Nederlof [WG 2019], we show that Cycle Cover parameterized by co-degeneracy admits a kernel with linear number of vertices. Besides that, we also show that Edge Dominating Set is FPT when parameterized by co-degeneracy. On the other hand, we remark that Graph Coloring is para-NP-complete when parameterized by co-degeneracy but FPT when parameterized by the co-treewidth. Concerning MaxCut, we give an FPT algorithm parameterized by co-treewidth, while we leave open its complexity when parameterized by co-degeneracy. Additionally, we show that Precoloring Extension is fixed-parameter tractable when parameterized by co-treewidth, while this problem is known to be W[1]-hard when parameterized by treewidth.
Banca examinadora:
Prof. Uéverton dos Santos Souza, UFF – Presidente
Prof. Fábio Protti, UFF
Prof. Luís Felipe Ignácio Cunha, UFF
Prof. Luerbio Faria, UERJ
Dr. Marcelo Rodrigues de Holanda Maia, IBGE