On (In)Tractability of Connection and Cut Problems
Authors:
Autores
| Person role | Person | |
|---|---|---|
|
7172 |
2872,257,2871,3147
|
|
|
7171 |
2872,257,2871,3147
|
|
|
7170 |
2872,257,2871,3147
|
|
|
7173 |
2872,257,2871,3147
|
Informations:
Pesc publication
Problemas de conexão e corte são problemas em grafos que foram amplamente estudados aos longos dos anos. Informalmente, problemas de conexão visam obter o menor/maior número de elementos necessários cuja inclusão resulte em um grafo conexo que satisfaça certas condições, enquanto que problemas de corte visam obter o menor/maior número de elementos necessários cuja remoção origine um grafo (desconexo) com mais componentes conexos. Nesta tese, abordamos problemas de conexão e corte sob a ótica de classes de grafos e complexidade computacional.
Especificamente, analisamos a complexidade do problema Conexão de terminais (TCP), que pode ser visto como uma generalização do problema clássico Árvore de Steiner. Propomos diversos resultados de complexidade para o TCP e para sua variante estrita (S-TCP), quando alguns dos parâmetros de entrada são fixos, e quando restritos a classes de grafos especificas, tais como grafos split, grafos de caminhos direcionados enraizados e grafos de clique-width limitado. Concentramo-nos especialmente em resultados que diferenciam a complexidade do TCP da complexidade do problema da Árvore de Steiner.
Ademais, analisamos a complexidade do problema clássico Corte máximo. Provamos que o problema é NP -completo em grafos de intervalo de contagem de intervalos igual a 4. Provamos também que Corte máximo é NP -completo em grafos de permutação. Este resultado resolve uma pergunta proposta por David S. Johnson, em Ongoing Guide to NP-completeness, que permanecia em aberto por diversos anos. Por fim, investigamos a complexidade do problema de computar o número de zig-zag de grafos direcionados. Provamos que k-zig-zag number está em NP para todo valor fixo de k, e que 2-zig-zag number é NP -completo.
Connection and cut problems are general graph problems widely studied over the years. Roughly, connection problems aim to obtain a minimum/maximum number of required elements whose inclusion yields a connected graph satisfying certain conditions, while cut problems aims to obtain a minimum/maximum number of required elements whose removal yields a (disconnected) graph with more connected components. This thesis addresses connection and cut problems from the perspective of graph classes and computational complexity.
Specifically, we analyse the computational complexity of Terminal connection (TCP), which can be seen as a generalisation of the classical Steiner tree problem. We propose several complexity results for TCP and for its strict variant (S-TCP), when some of the input parameters are fixed, and they are restricted to specific graph classes, such as split graphs, rooted directed path graphs, and graphs of bounded clique-width. We mainly concentrate on results that differentiate the complexity of TCP from the complexity of Steiner tree.
Additionally, we analyse the computational complexity of the classical MaxCut problem. We propose the first complexity classification for the problem with respect to interval graphs of bounded interval count, by proving that it remains NP -complete on interval graphs of interval count 4. We also prove that MaxCut is NP -complete on permutation graphs, settling a long-standing open question from Ongoing Guide to NP-completeness by David S. Johnson. Finally, we investigate the complexity of computing the zig-zag number of a directed graph, which is a directed width measure defined over cuts of a graph. We prove that k-zig-zag number is in NP for every fixed k, and that 2-zig-zag number is already an NP -complete problem.