Computational complexity of graph compaction
Pavol Hell, Narayan Vikas · 1997
We say that a graph is reflexive if each of its vertices has a loop, and irreflexive if none of its vertices has a loop. Any graph, in general, is said to be partially reflexive. In the following, let G and H be graphs. A homomorphism $f:G\to H,$ of G to H, is a mapping f of the vertices of G to the vertices of H, such that $f(g)$ and $f(g\sp\prime)$ are adjacent vertices of H whenever g and $g\sp\prime$ are adjacent vertices of G. A compaction $c:G\to H,$ of G to H, is a homomorphism of G to H, such that for every vertex x of H, there exists a vertex v of G with $c(v)=x,$ and for every edge $hh\sp\prime$ of $H, h ot=h\sp\prime,$ there exists an edge $gg\sp\prime$ of G with $c(g)=h$ and $c(g\sp\prime)=h\sp\prime.$ If there exists a compaction of G to H then G is said to compact to H. Let H be a fixed graph. The problem of deciding the existence of a compaction to H, called the compaction problem for H, and denoted as COMP-H, is the following: Instance: A graph G. Question: Does G compact to H? We show that COMP-H is NP-complete when H is a reflexive k-cycle, for all $k\ge4.$ In particular, for $k=4,$ this solves a widely publicised open problem posed by Winkler in 1988. When H is a reflexive chordal graph (which includes the case of a reflexive 3-cycle), we observe that COMP-H is polynomial time solvable. We also show that COMP-H is NP-complete when H is an irreflexive even k-cycle, for all even $k\ge6.$ Determining the complexity of COMP-H when H is an irreflexive even k-cycle, for any particular even $k\ge6,$ has also been considered before for a long time. When H is a non-bipartite irreflexive graph (which includes the case of irreflexive odd cycles), we notice that COMP-H is NP-complete. When H is a chordal bipartite graph (which includes the case of an irreflexive 4-cycle), we point out that COMP-H is polynomial time solvable. We further show that COMP-H is NP-complete when H is a path of length k, with loops on its first and last vertices only, for all $k\ge2.$ Using this result, we prove NP-completeness of COMP-H for some other partially reflexive graphs H also. When H is a forest with trees $H\sb1,H\sb2,\...,H\sb{s},$ such that the set of vertices with loops in $H\sb{i}$ induces a connected subgraph of $H\sb{i},$ for all $i=1,2,\...,s,$ we note that COMP-H is polynomial time solvable. We give a complete complexity classification of COMP-H when H is any (partially reflexive) graph with four or fewer vertices, showing that COMP-H is either polynomial time solvable or NP-complete. (Abstract shortened by UMI.)