Computational complexity of generalized graph coloring problems
Christos H. Papadimitriou, V. Rutenburg · Stanford University eBooks · 1988
In this work we study a wide class of problems in graph theory, called generalized node-coloring problems, defined as follows: given graphs $G$ and $H$, can the nodes of $H$ be colored with $k$ colors to avoid containing $G$ as a subgraph in each color component? For each fixed choice of $G$ and $k$, we denote such problem as the generalized coloring problem with respect to $G$ and $k$, or GCP$\sb{G,k}$. When $G$ is $K\sb2$ (i.e., a single edge), then GCP$\sb{K\sb2,k}$ becomes the ordinary node-coloring problem (OCP$\sb{k}$). Therefore, the class of problems we consider is a natural generalization of the OCP, generalizing the forbidden subgraph from $K\sb2$ to an arbitrary one. The generalized coloring problems are abstractions of graph partitioning problems that are of interest in distributed operating systems, constraint satisfaction in artificial intelligence, VLSI design, and resource allocation. We completely characterize the complexity of the class of generalized coloring problems GCP$\sb{G,k}$. In fact, this characterization is a special case of our complete characterization of the class of all the problems of avoiding any nontrivial finite family of graphs $F$ (denoted GCP$\sb{F,k}$), rather than a single graph. We prove that all such problems are NP-complete for three or more colors. For two colors, they are NP-complete when $F$ does not contain a graph of maximum degree one. Otherwise, it is in ${\cal P}$, and we exhibit a polynomial-time (in fact, ${\cal NC}$) algorithm for the solution of such problems. We also consider what happens when $G$ is part of the input. This problem, denoted $GCP\sb{k}$, can be viewed as the composition of an NP-complete problem with a co-NP-complete problem. We show that, in this case, deciding whether $H$ can be colored (even with two colors) to avoid $G$ is $\Sigma\sbsp{2}{p}$-complete. This result involves an interesting extension of our reduction techniques, and appears to be the first natural graph problem known to be complete for an intermediate level of the polynomial hierarchy. The same techniques can be generalized to prove the $\Sigma\sbsp{2}{p}$-completeness of other related problems, including that of the Generalized Node Deletion Problem with forbidden subgraphs being part of the input. This theorem is an extension of the results of Yannakakis, who proved NP-hardness of Node Deletion Problems with fixed forbidden graphs. This result is in turn used in establishing the $\Sigma\sbsp{2}{p}$-completeness of the Clause Maintenance System, an important paradigm in artificial intelligence.