Reconhecimento de grafos IIC-comparabilidade

Abstract

Resumo: As relações binárias que são reflexivas, antissimétricas e transitivas são o que chamamos de ordem parcial. Podemos representar ordens parciais através de grafos de comparabilidade. Um grafo de comparabilidade é fechado sob interseção de intervalos (IIC) (Groshaus e Guedes, 2021) se, para cada vértice do grafo, o intervalo de predecessores e o intervalo de sucessores são fechados sob interseção. Em Groshaus e Guedes (2021), viu-se que é necessário que todo C4 tenha um vértice central universal, formando uma 4-roda, para que algum grafo de comparabilidade seja IIC. Nesta dissertação apresentamos mais uma propriedade dessa classe que generaliza esse resultado para C4s consecutivos e formulamos um algoritmo de reconhecimento da classe em programação linear inteira. Apesar disso, ainda não sabemos se o reconhecimento desta classe pode ser feito em tempo polinomial ou se é um problema NP-completo.

Abstract: Binary relations that are reflexive, antisymmetric and transitive are what we call partial orders. We can represent partial orders through comparability graphs. A comparability graph is interval intersection closed (IIC) (Groshaus e Guedes, 2021) if, for any vertice of the graph, the predecessors interval and successors interval are closed under intersection. In Groshaus e Guedes (2021), its been shown that every C4 must have a central universal vertice, forming a 4-wheel, for a comparability graph to be IIC. In this dissertation we present a new property of the class that generalizes this result to consecutive C4s and we formulate a recognition algorithm for the class using integer linear programming. Nevertheless, its still an open problem if the recognition of this class can be done in polinomial time or if its a NP-complete problem.