On the Complexity of the Set Graph Recognition Problem Restricted to Cographs and Split Graphs
Autores
|
7193 |
3152,410
|
|
|
7194 |
3152,410
|
Informações:
Publicações do PESC
Nesta dissertação, tratamos do problema de reconhecimento de set graphs, isto é, o problema de decidir se um dado grafo é, ou não, um set graph. Este problema, também conhecido como problema da orientação extensional acíclica (EAO), foi provado ser NP-completo por A. Tomescu em 2012. Como é de costume, parte da pesquisa sobre o problema é determinar se esse problema pode ser resolvido em tempo polinomial quando restrito a certas classes de grafos, e assim, fazer um mapeamento da complexidade do problema quando restrito a cada classe de grafos. Primeiro, apresentamos o tema, junto a uma coletânea de resultados relevantes ao seu desenvolvimento. Segundo, desenvolvemos algumas ferramentas auxiliares para o reconhecimento de set graphs. Definimos as orientações extensionais-por-camadas acíclicas e um parâmetro chamado set-deficiency, que mede o quão distante um grafo está de ser um set graph. Terceiro, usamos as ferramentas descritas na elaboração de um algoritmo de tempo polinomial para reconhecer set graphs na classe de cografos. Quarto, provamos que o reconhecimento de set graphs restrito à classe dos grafos split é NP-completo.
In this dissertation, we study the set graph recognition problem, i.e., the problem of deciding whether a given graph is a set graph or not. This problem, also known as the extensional acyclic orientation problem (EAO), was proved to be NP-complete by A. Tomescu in 2012. As usual, part of the research on this topic is to determine whether EAO becomes solvable by polynomial-time algorithms when restricted to certain graph classes. First, we present the context of the problem, with a collection of results that are relevant to this line of research. Second, we develop some auxiliary tools for the recognition of set graphs. We define the layered extensional acyclic orientations and a graph parameter called set-deficiency, that measures how far a graph is from being a set graph. Third, we apply the developed tools to reach a polynomial-time algorithm for recognizing set graphs in the class of cographs. Fourth, we prove that the recognition of set graphs restricted to split graphs is NP-complete.