Partitioning a Graph into Complementary Subgraphs

摘要

In the Partition Into Complementary Subgraphs (Comp-Sub) problem we are given a graph G = (V, E), and an edge set property 77, and asked whether G can be decomposed into two graphs, 77 and its complement H, for some graph 77, in such a way that the edge cut-set (of the cut) [V(H), V(H)] satisfies property Ⅱ. Such a problem is motivated by the fact that several parameterized problems are trivially fixed-parameter tractable when the input graph G is decomposable into two complementary subgraphs. In addition, it generalizes the recognition of complementary prism graphs, and it is related to graph isomorphism when the desired cut-set is empty, Comp-Sub(?). In this paper we are particularly interested in the case Comp-Sub(?), where the decomposition also partitions the set of edges of G into 75(77) and E(H). We show that Comp-Sub(?) is Gl-complete on chordal graphs, but it becomes more tractable than Graph Isomorphism for several subclasses of chordal graphs. We present structural characterizations for split, starlike, block, and unit interval graphs. We also obtain complexity results for permutation graphs, cographs, comparability graphs, co-comparability graphs, interval graphs, co-interval graphs and strongly chordal graphs. Furthermore, we present some remarks when 77 is a general edge set property and the case when the cut-set M induces a complete bipartite graph.