Computational Complexity Relationship between Compaction, Vertex-Compaction, and Retraction

摘要

In this paper, we show a very close relationship between the compaction, vertex-compaction, and retraction problems for reflexive and bipartite graphs. The relationships that we present relate to a long-standing open problem concerning whether any pair of these problems are polynomially equivalent for every graph. The relationships we present also relate to the constraint satisfaction problem, providing evidence that similar to the compaction and retraction problems, it is also likely to be difficult to give a complete computational complexity classification of the vertex-compaction problem for every reflexive or bipartite graph. In this paper, we however give a complete computational complexity classification of the vertex-compaction problem for all graphs, including even partially reflexive graphs, with four or fewer vertices, by giving proofs based on mostly just knowing the computational complexity classification results of the compaction problem for such graphs determined earlier by the author. Our results show that the compaction, vertex-compaction, and retraction problems are polynomially equivalent for every graph with four or fewer vertices.