Computational aspects of greedy partitioning of graphs

Partitioning a graph into smaller parts is one of the fundamental algorithmic techniques and often an important part of more general tasks like parallelization, complexity reduction or simply a single step of divide-and-conquer algorithm. Over the years graph partitioning has been a subject of many variations and generalizations but it has been usually understood as partitioning the vertex set of a graph such that certain objective is met, e.g., it is possible to seek partitions into a given number of equal-sized sets such that the number of edges having endvertices in distinct sets is minimized or, as in this paper, one can minimize the number of the resulting sets under assumption that each set induces a graph with appropriate property.

Our main concern is the computational complexity of several problems related to greedy partitioning the vertex set of simple, finite and undirected graphs in such a way that each of the resulting sets induces a graph in some fixed hereditary class of graphs.

Introducing critical partitions and describing their structural properties we step towards a general technique that benefits from the knowledge of polynomial-time approximation algorithms for diverse optimization problems with inputs in certain graph classes, called basic classes. We use such algorithms to develop new polynomial-time approximation algorithms that can be applied to all inputs in carefully constructed superclasses of the basic classes. Our approach ensures that extending basic classes of inputs we preserve the order of approximation ratios of the original algorithms. More formally, let \({{\mathcal {C}}({\mathcal {{\mathcal {P}}}},k)}\) denote the class of graphs \({\mathcal {P}}\)-colorable with at most k colors and let \((V_1,\ldots ,V_k)\) be a \({\mathcal {P}}\)-coloring of an arbitrary graph \(G\in {{\mathcal {C}}({\mathcal {{\mathcal {P}}}},k)}\). Now, consider a minimization problem \(\varPi \) for which there is a polynomial-time \(\delta (n)\)-approximation algorithm \({{\texttt {A}}}_1\) for inputs in \({\mathcal {P}}\). Naturally, since \(G[V_i]\in {\mathcal {P}}\), the algorithm \({{\texttt {A}}}_1\) can be directly applied to each \(G[V_i]\). Additionally, assume that there exists a polynomial-time algorithm \({{\texttt {A}}}_2\) that, given the outputs of \({{\texttt {A}}}_1\) for each input \(G[V_i]\) gives a solution of \(\varPi \) for G such that \({{\texttt {A}}}_1(G)\le k\cdot \max \{{{\texttt {A}}}_1(G[V_i]) \mid 1\le i \le k\}\), where \({{\texttt {A}}}_1(G[V_i])\) denotes the worst-case cost of the solution produced by \({{\texttt {A}}}_1\) for \(G[V_i]\). We say that \(\varPi \) is a problem with compositive solutions if such an algorithm \({{\texttt {A}}}_2\) exists (note that such algorithms can be easily given for various domination and coloring problems). A major drawback of such a three-phase approach (partition, solve, compose) is that we do not know any simple realization of this procedure, because, with a sole exception of proper 2-Coloring, the \({\mathcal {P}}\)-coloring problem is computationally hard (see Brown 1996; Kratochvíl and Schiermeyer 1997). Furthermore, our knowledge of minimal forbidden subgraphs that characterize \({\mathcal {C}}({\mathcal {P}},k)\) is far from being complete (for some recent results in context of proper k-coloring of graphs in selected classes, mainly for \(k\in \{3,4\}\), see, e.g., Hoàng et al. (2015), Chudnovsky et al. (2016), and Goedgebeur and Schaudt (2016)). This directs our attention to the class \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k)}\) consisting of all graphs for which \({\varGamma _{\mathcal {P}}(G)}\le k\). Naturally, for every \(k\ge 2\) we have \({\mathcal {P}}\subset {{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k)}\subset {{\mathcal {C}}({\mathcal {{\mathcal {P}}}},k)}\). Hence, the class \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k)}\) is an extension of \({\mathcal {P}}\) and offers an intrinsic algorithmic property of its members to be greedily \({\mathcal {P}}\)-colorable with at most k colors. Therefore, the algorithm that follows the above-mentioned three phases and uses greedy \({\mathcal {P}}\)-coloring routine in the first phase (we denote this algorithm by \({{\texttt {PH}}}\)), can be used for all inputs in \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k)}\) and achieves an approximation ratio of the same order as \({{\texttt {A}}}_1\) for inputs in \({\mathcal {P}}\). For an illustration of the above concept see Fig. 1.

In what follows we also use a fact that every \({\mathcal {P}}\)-coloring \((V_1,\ldots ,V_k)\) of a graph G with k colors can be seen as a surjection \({\varphi :V(G)}\rightarrow \{1,\ldots ,k\}\) such that \(\varphi (v)=i\) for every vertex \(v\in V_i\) (for brevity we also say that \(\varphi \) is a \({\mathcal {P}}\)-coloring). A subset U of vertices of a graph G is strongly  \({\mathcal {P}}\)-dominating in G if for every vertex \(v\in V(G)\setminus U\) there exists a set \(D\subseteq U\) such that \(G[D\cup \{v\}]\in {\varvec{F}}({\mathcal {P}})\).

The above proposition reveals the importance of specific bipartition of the vertex set in which both parts have certain coloring or domination properties. We focus on how they come into play in graphs that are minimal with respect to the \({\mathcal {P}}\)-Grundy number under taking induced subgraphs. For \(k\ge 1\) by \({{\mathcal {U}}({\mathcal {P}},k)}\) we denote the class of graphs G for which \({\varGamma _{\mathcal {P}}(G)} \ge k\). Naturally \({{\mathcal {U}}({\mathcal {P}},k)} = {\mathcal {I}}\setminus {{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k-1)}\) (recall that \({\mathcal {I}}\) denotes the class of all graphs). In what follows \({\varvec{C}}_k({\mathcal {P}})\) stands for the family of minimal graphs in the class \({{\mathcal {U}}({\mathcal {{\mathcal {P}}}},k)}\), that is, the graphs for which \({\varGamma _{\mathcal {P}}(G)} = k\) and \({\varGamma _{\mathcal {P}}(G-v)} < k\), where v is an arbitrary vertex of G. Note that \({\varvec{C}}_1({\mathcal {P}})=\{K_1\}\), \({\varvec{C}}_2({\mathcal {P}})={\varvec{F}}({\mathcal {P}})\) and that forbidding all graphs in \({\varvec{C}}_k({\mathcal {P}})\) defines \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k-1)}\); more formally \({\varvec{C}}_k({\mathcal {P}})={\varvec{F}}({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k-1)})\). Minimal graphs play a crucial role in the greedy coloring process; in fact they determine the number of colors used by the greedy algorithm in the worst case, and they characterize classes \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},k)}\). For proper coloring the classes \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},2)}\) and \({{\mathcal {G}}({\mathcal {{\mathcal {P}}}},3)}\) were characterized by Gyárfás et al. (1979) who proved that \({\varvec{C}}_{3}({\mathcal {P}})=\{K_3,P_4\}\) and listed all 22 graphs in \({\varvec{C}}_{4}({\mathcal {P}})\).

The key notion in our analysis of minimal graphs is a class \({\mathcal {F}}({\mathcal {P}},k)\) consisting of all graphs G for which there exists a partition (I, C) of V(G) such that I is nonempty, \({\mathcal {P}}\)-independent and strongly \({\mathcal {P}}\)-dominating in G, and \(G[C]\in {\varvec{C}}_{k-1}({\mathcal {P}})\), where \(k\ge 2\). Such a partition is called a critical partition of the graph G. Note that critical partition of G does not have to be unique.

In what follows, we have to carefully distinguish between the two important cases of finite and infinite family \({\varvec{F}}({\mathcal {P}})\). In this section we prove that if \({\varvec{F}}({\mathcal {P}})\) is finite, then Grundy  \(({\mathcal {P}},k)\) -Coloring can be solved in polynomial time.

In what follows we need the class \({\mathcal {T}}({\mathcal {P}},k)\) of forcing  \(({\mathcal {P}},k)\)-trees. Namely, if \(k=2\), then \({\mathcal {T}}({\mathcal {P}},2)={\varvec{C}}_2({\mathcal {P}})\). For \(k\ge 3\) let B be a graph in \({\mathcal {T}}({\mathcal {P}},k-1)\) and let \(F_1,\ldots ,F_{n(B)}\) be disjoint graphs, each being isomorphic to a graph in \({\varvec{F}}({\mathcal {P}})\). A graph G belongs to \({\mathcal {T}}({\mathcal {P}},k)\) if it can be obtained from \(B,F_1,\ldots ,F_{n(B)}\) by an identification of each vertex of B with an arbitrary vertex of some graph \(F_j\), \(j\in \{1,\ldots ,n(B)\}\) in such a way that every \(F_j\) takes part in exactly one identification. As the root of forcing \(({\mathcal {P}},k)\)-tree we select an arbitrary vertex of \(B\in {\mathcal {T}}({\mathcal {P}},2)\). All graphs in \({\mathcal {T}}({\mathcal {P}},k)\) are minimal in the class \({\mathcal {F}}({\mathcal {P}},k)\) for every \(k\ge 2\) (see Borowiecki 2006).

The above finite basis theorem allows the proof of the following result on the computational complexity of Grundy  \(({\mathcal {P}},k)\) -Coloring.

In this section we prove that Grundy \({\mathcal {P}}\) -Coloring is \(\mathbb {NP}\)-complete for every class \({\mathcal {P}}\) defined by \({\varvec{F}}({\mathcal {P}})=\{K_p\}\) with \(p\ge 3\).

In our proof we use a polynomial-time reduction from 3-Coloring of planar graphs with vertex degree at most 4 (for \(\mathbb {NP}\)-completeness see Garey et al. (1976)). In fact we need a slight strengthening of their result consisting in restricting the class to planar graphs with vertex degree at most 4, size \(m\equiv 1(\text{ mod } r)\) and every vertex belonging to at least one triangle; the class of such graphs we denote by \({\mathcal {L}}(r)\).

For a proof of Theorem 4.1 we refer the reader to “Appendix A”.

In order to prove the above theorem we give Construction 4.1 and prove several lemmas. Let \(p\ge 3\), \({\varvec{F}}({\mathcal {P}})=\{K_p\}\), and let G be an instance of 3-Coloring in \({\mathcal {L}}(p-1)\). We construct a graph \(G^\prime \) and calculate an integer k such that \(G^\prime \) has a Grundy \({\mathcal {P}}\)-coloring with k colors if and only if G has a proper 3-coloring.

We say that in a \({\mathcal {P}}\)-colored graph H a set \(U\subseteq V(H)\) uses color \(\ell \) if every vertex in U has color \(\ell \).

For a rather technical proof of Lemma 4.2 we refer the reader to “Appendix B”.

Let \(V_1\), \(V_2\) be two nonempty vertex sets of the same cardinality, and let \(\ell _1\), \(\ell _2\) be two distinct colors. We say that \(V_1\), \(V_2\) mix colors \(\ell _1\) and \(\ell _2\) if there exists a partition \((A_1,A_2)\) of \(V_1\cup V_2\) such that \(\vert A_1\vert = \vert A_2\vert \), \(A_1\ne V_i\) and \(A_i\) uses \(\ell _i\), \(i\in \{1,2\}\). The next lemma says that certain vertex sets of \(G^\prime \) cannot mix colors.

In this section we investigate the computational complexity of the problem of deciding the membership in the class \({\mathcal {H}}({\mathcal {P}},t)=\{G\!\mid \!{\varGamma _{\mathcal {P}}(G)}-\chi _{{\mathcal {P}}}(G)\le t\}\). We prove that the problem is \(\text {co}\mathbb {NP}\)-complete for every \(t\ge 0\) and every class \({\mathcal {P}}\) for which \({\varvec{F}}({\mathcal {P}})=\{K_p\}\) with \(p\ge 3\). We present a polynomial-time reduction from Grundy  \({\mathcal {P}}\) -Coloring of graphs in the class \({\mathcal {Q}}(p-1)\), where by \({\mathcal {Q}}(p-1)\) we mean the class of graphs obtained by the application of Construction 4.1 to all graphs G in \({\mathcal {L}}(p-1)\) for which \(m(G)\ge 4p-3\) (note that such a restriction on the size of graphs does not influence the hardness of Grundy  \({\mathcal {P}}\) -Coloring, i.e., it remains \(\mathbb {NP}\)-complete even in \({\mathcal {Q}}(p-1)\)). Before proving the hardness of the above membership problem we need some facts on the \({\mathcal {P}}\)-Grundy number of graphs in \({\mathcal {Q}}(p-1)\).

In what follows we use the following properties of \(H_t\) with \(t\ge 0\).

The former equation follows easily by the fact that every forcing \(({\mathcal {P}},t+1)\)-tree admits a \({\mathcal {P}}\)-coloring with 2 colors. For a lower bound in the latter one it is enough to consider one of the “from the leaves up” orderings, that forces the greedy algorithm to use \(t+1\) colors on each of the forcing \(({\mathcal {P}},t+1)\)-trees \(T_1,\ldots ,T_{n(G)}\) while an upper bound follows by the analysis of graphs F in \({\varvec{C}}_k({\mathcal {P}})\) contained in \(H_t\) and such that \(k>\chi _{{\mathcal {P}}}(F)\).

First, let \(\chi _{{\mathcal {P}}}(G)\ge \kappa \). Naturally, \(\chi _{{\mathcal {P}}}(G)\ge \kappa \) implies \({\varGamma _{\mathcal {P}}(G)}\ge \kappa \) and hence \((G,\kappa )\) is a Yes instance of Grundy  \({\mathcal {P}}\) -Coloring. Since by Remark 5.1 for every graph \(G\in {\mathcal {Q}}(p-1)\) we have \(\chi _{{\mathcal {P}}}(G) < {\varGamma _{\mathcal {P}}(G)}\), by (i) and (ii) we get \( \chi _{{\mathcal {P}}}(G^\prime ) = \chi _{{\mathcal {P}}}(G) < {\varGamma _{\mathcal {P}}(G)} = {\varGamma _{\mathcal {P}}(G^\prime )} - t \) (recall \(G^\prime =H_t\)). Thus \(G^\prime \notin {\mathcal {H}}({\mathcal {P}},t)\); in other words \(G^\prime \) is a Yes instance of the problem of the membership in \({\mathcal {I}}\setminus {\mathcal {H}}({\mathcal {P}},t)\).

Next, assume \(\chi _{{\mathcal {P}}}(G) < \kappa \). Let us consider a graph \(H^\prime = H_t + G^\prime [S]\). It is not hard to see that \(\chi _{{\mathcal {P}}}(H^\prime ) \le \chi _{{\mathcal {P}}}(H_t)+1\) and hence by (i) we easily get \(\chi _{{\mathcal {P}}}(H^\prime )\le \chi _{{\mathcal {P}}}(G)+1\). On the other hand, \(\chi _{{\mathcal {P}}}(H^\prime ) \ge \lceil \omega (H^\prime )/(p-1) \rceil \). Since \(\omega (H^\prime ) = \omega (H_t) + p - 1\) and \(\omega (H_t)=\omega (G)\), we have \(\chi _{{\mathcal {P}}}(H^\prime ) \ge \lceil \omega (G)/(p-1) \rceil + 1\), which, by Lemma 5.1, results in \(\chi _{{\mathcal {P}}}(H^\prime ) \ge \chi _{{\mathcal {P}}}(G) + 1\). Finally, \(\chi _{{\mathcal {P}}}(H^\prime ) = \chi _{{\mathcal {P}}}(G)+1\).

Now, consider \(G^\prime \) and observe that \(\chi _{{\mathcal {P}}}(G^\prime ) = \max \{\chi _{{\mathcal {P}}}(H^\prime ), \chi _{{\mathcal {P}}}(K)\}\). Hence, since \(\chi _{{\mathcal {P}}}(K)=\kappa \) and by assumption \(\chi _{{\mathcal {P}}}(G) < \kappa \), we getMoreover, by Proposition 2.2 and simple analysis of maximum degrees of appropriate subgraphs of \(G^\prime \) we see that \({\varGamma _{\mathcal {P}}(H^\prime )} = {\varGamma _{\mathcal {P}}(H_t)} + 1\). A similar argument results in \({\varGamma _{\mathcal {P}}(G^\prime )} = \max \{{\varGamma _{\mathcal {P}}(H^\prime )}, {\varGamma _{\mathcal {P}}(K)} \}\), and since \({\varGamma _{\mathcal {P}}(K)} = \kappa \) and by (ii) we have \({\varGamma _{\mathcal {P}}(H_t)} = {\varGamma _{\mathcal {P}}(G)} + t\), we see thatNow, we continue by considering the two possibilities. If \({\varGamma _{\mathcal {P}}(G)}\ge \kappa \), then \( {\varGamma _{\mathcal {P}}(G^\prime )} \ge \max \{\kappa + t + 1, \kappa \} = \kappa + t + 1 > \chi _{{\mathcal {P}}}(G^\prime ) + t, \) which implies \(G^\prime \notin {\mathcal {H}}({\mathcal {P}},t)\). On the other hand, if \({\varGamma _{\mathcal {P}}(G)}<\kappa \), then \( {\varGamma _{\mathcal {P}}(G^\prime )} \le \max \{\kappa -1+ t + 1, \kappa \} = \kappa + t = \chi _{{\mathcal {P}}}(G^\prime ) + t \) and hence \(G^\prime \in {\mathcal {H}}({\mathcal {P}},t)\).

Thus \(G^\prime \notin {\mathcal {H}}({\mathcal {P}},t)\) if and only if \({\varGamma _{\mathcal {P}}(G)}\ge \kappa \). \(\square \)

We conclude our paper with a new upper bound on the \({\mathcal {P}}\)-Grundy number. For clarity of presentation first we recall some notation introduced in the proof of Lemma 4.2 (see “Appendix B”). For a vertex v of a graph G we use \({\mathcal {D}}(G,v)\) to denote the family of all subsets of \(V(G)\setminus \{v\}\) such that \(G[D\cup \{v\}]\in {\varvec{F}}({\mathcal {P}})\) holds for every D in \({\mathcal {D}}(G,v)\). The set \({N_{G}({\mathcal {P}},v)} = \{u\in D \mid D \text{ is } \text{ a } \text{ member } \text{ of } {\mathcal {D}}(G,v)\}\) is called the \({\mathcal {P}}\)-neighborhood of vertex v in G. By the \({\mathcal {P}}\)-degree of a vertex v of G, denoted by \({d_{G}({\mathcal {P}},v)}\), we mean the cardinality of a largest subfamily of \({\mathcal {D}}(G,v)\) consisting of pairwise disjoint sets.

A natural upper boundfollows directly from the greedy color assignment rule. The above bound, however, can be significantly improved by careful analysis of function \({\phi }_{G}:V(G)\rightarrow \mathbb {N}_0\) defined recursively on the vertex set of a graph G. Namely, let \({{\phi }^{0}_{G}({\mathcal {P}},v)} = {d_{G}({\mathcal {P}},v)}\). For every integer \(r\ge 1\), let \({{\phi }^{r}_{G}({\mathcal {P}},v)}\) be the largest k for which there exist k pairwise disjoint sets \(D_1,\ldots ,D_k\) in \({\mathcal {D}}(G,v)\) such that for each of them \({\lambda ^{r-1}_{G}(D_i)}\ge i\), where \({\lambda ^{r-1}_{G}(D_i)}\) denotes the \((r-1)\)st intensity of \(D_i\) defined as followswhere \(i\in \{1,\ldots ,k\}\). A simple inductive argument shows that \({{\phi }^{r}_{G}({\mathcal {P}},v)}\le {{\phi }^{r-1}_{G}({\mathcal {P}},v)}\) for every vertex v and every \(r\ge 1\). This implies the existence of an integer \(t\ge 0\) such that \({{\phi }^{t}_{G}({\mathcal {P}},v)}={{\phi }^{r}_{G}({\mathcal {P}},v)}\) for every vertex v and every \(r\ge t\). Thus \({{\phi }^{t}_{G}({\mathcal {P}},v)}\) is uniquely determined. The \({\mathcal {P}}\)-potential of a vertex v, denoted by \({{\phi }^{}_{G}({\mathcal {P}},v)}\), is given by \( {{\phi }^{}_{G}({\mathcal {P}},v)}={{\phi }^{t}_{G}({\mathcal {P}},v)}. \) The \({\mathcal {P}}\)-potential of a graph G, denoted by \({{\varPhi }_{\mathcal {P}}(G)}\), is defined as followsLet us consider a simple example.

For the proof of Theorem 6.1 we need the following property.