| 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:Gto 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(gspprime)$ are adjacent vertices of H whenever g and $gspprime$ are adjacent vertices of G. A compaction $c:Gto 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 $hhspprime$ of $H, hnot=hspprime,$ there exists an edge $ggspprime$ of G with $c(g)=h$ and $c(gspprime)=hspprime.$ 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 $kge4.$ 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 $kge6.$ Determining the complexity of COMP-H when H is an irreflexive even k-cycle, for any particular even $kge6,$ 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 $kge2.$ 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 $Hsb1,Hsb2,...,Hsb{s},$ such that the set of vertices with loops in $Hsb{i}$ induces a connected subgraph of $Hsb{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.). |
