Problema de particionamento em subgrafos complementares: complexidade e convexidade
Nenhuma Miniatura disponível
Data
2019-11-11
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
In this work, we introduce the PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB(Pi))
problem, which receives as input a graph H and an edge set property Pi, and the goal is determining
whether is possible to decompose the graph H into complementary subgraphs G and \bar{G} such that the
edge set M between G and \bar{G} satisfies property Pi. COMP-SUB(Pi) generalizes the recognition of
complementary prisms problem, which is the case when Pi is a perfect matching between corresponding
vertices of G and \bar{G}. When Pi is arbitrary, we show results for k-clique or k-independent set free
graphs. On property P_\emptyset which considers M =\emptyset, we show that COMP-SUB(P_\emptyset)
is GI-complete for chordal graphs, but can be solved efficiently for permutation, comparability, co-
comparability and co-interval graphs. Furthermore, we obtain characterizations for some subclasses of
chordal graphs. We also obtain results for Pi_{Kn,n} , the case when M has all the possible edges between
G and \bar{G} and for Pi_{PERF}, the case which considers M as a perfect matching. In particular, we
show that COMP-SUB(Pi_{PERF}) problem is GI-hard, and we obtain characterizations for this problem
when the input graph H is a cograph, a chordal or a distance-hereditary graph. On the other hand, we
address three parameters of the geodetic convexity for complementary prisms: the hull number, the geodetic
number and the convexity number. We obtain results on the hull number for complementary prisms
G\bar{G} when both G e \bar{G} are connected. On the second and third parameter, we show that the
decision problems related to the geodetic number and convexity number are NP-complete even restricted to
complementary prisms. We also establish lower bounds on the geodetic number for G\bar{G} when G or
\bar{G} have simplicial vertices and we determine the convexity number for G\bar{G} when G is
disconnected, or G is a cograph.
Descrição
Citação
NASCIMENTO, J. R. Problema de particionamento em subgrafos complementares: complexidade e convexidade. 2019. 129 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Foiânia, 2019.