Minimum Sum Coloring with Bundles in Trees and Bipartite Graphs

It is easy to see that Minimum Sum Coloring with Bundles is in NP. To prove NP-hardness, we reduce Independent Set to Minimum Sum Coloring with Bundles. Here, for an undirected graph $G=(V,E)$, we say that $S\subseteq V$ is independent if $G$ has no edge connecting the vertices in $S$.

Problem:

Independent Set

Input:

An undirected graph $G=(V,E)$ and a positive integer $k\in {\mathbb{Z}}_{>0}$.

Question:

Determine whether there exists an independent set $S\subseteq V$ with $|S|\ge k$.

It is well-known that Independent Set is NP-complete (see [16]).

Suppose that we are given an instance of Independent Set that consists of a graph $G=(V,E)$ and a positive integer $k$. We construct a new graph $G^{\prime }=(V^{\prime },E^{\prime })$ by replacing each vertex $v\in V$ with $|{\delta }_G(v)|$ new vertices so that each new vertex has exactly one incident edge. Formally, $G^{\prime }$ is defined as follows:

Let $B_v:=\{p_{(v,e)}\mid e\in {\delta }_G(v)\}$ for each $v\in V$, and define $ℬ=\{B_v\mid v\in V\}$. Then, it is easy to see that $E^{\prime }$ forms a perfect matching in $G^{\prime }$ and $ℬ$ is a partition of $V^{\prime }$. Let $w(B)=1$ for any $B\in ℬ$, and let $C=2|V|-k$. This defines an instance $(G^{\prime },ℬ,w,C)$ of Minimum Sum Coloring with Bundles. See Figure 2.

To show the validity of this reduction, it suffices to show that $G$ has an independent set of size at least $k$ if and only if there exists a coloring $c$ of $G^{\prime }$ such that ${\sum }_{v\in V}\max \{c(p)\mid p\in B_v\}\le C$.

We first show the sufficiency (“if” part). Suppose that $G^{\prime }$ has a coloring $c:V^{\prime }\to {\mathbb{Z}}_{>0}$ such that $cost(c)\le C=2|V|-k$. Let $S:=\{v\in V\mid \max \{c(p)\mid p\in B_v\}=1\}$. Then, since

we obtain $|S|\ge k$. For any edge $e=uv\in E$, since $c(p_{(u,e)})\ne c(p_{(v,e)})$ as $c$ is a coloring, at least one of $c(p_{(u,e)})\ge 2$ and $c(p_{(v,e)})\ge 2$ holds, which implies that at least one of $u$ and $v$ is in $V\setminus S$. Therefore, $S$ is an independent set in $G$, which shows the sufficiency.

We next show the necessity (“only if” part). Suppose that $G$ has an independent set $S\subseteq V$ with $|S|\ge k$. Let $c:V^{\prime }\to {\mathbb{Z}}_{>0}$ be a coloring of $G^{\prime }$ such that

• $\mathrm{■}$

  for each edge $e=uv\in E$, one of $c(p_{(u,e)})$ and $c(p_{(v,e)})$ is $1$ and the other is $2$, and

• $\mathrm{■}$

  for any $v\in S$ and any $e\in {\delta }_G(v)$, it holds that $c(p_{(v,e)})=1$.

Note that such a coloring $c$ exists, because $S$ is an independent set in $G$. Since $\max \{c(p)\mid p\in B_v\}=1$ for $v\in S$ and $\max \{c(p)\mid p\in B_v\}\le 2$ for $v\in V\setminus S$, we obtain

which shows the necessity.

Therefore, the reduction is valid, and hence Minimum Sum Coloring with Bundles is NP-hard even when the edge set forms a perfect matching, $ℬ$ is an independent partition of the vertex set, and $w(B)=1$ for every $B\in ℬ$. $◀$

We then prove the NP-hardness of Minimum Sum Coloring with Bundles on paths by reducing Minimum Sum Coloring with Bundles with the conditions in Theorem 2. Roughly speaking, the reduction involves creating four copies of the instance described in Theorem 2 and carefully connecting their edges to form a single path. See the full version for details.

The proof proceeds by induction on $|ℬ|$. Consider the case where $|ℬ|=1$ and $ℬ=\{B\}$. Note that $B=V$ as each vertex is contained in some bundle. Let $c$ be a minimum coloring, i.e., a coloring that attains $\chi (G)$. Then, ${\max }_{v\in B}c(v)\le {\max }_{v\in V}c(v)=\chi (G)=\chi (G)|ℬ|$.

Now, let $\mathrm{\ell }\ge 1$ be a positive integer, and assume that the lemma holds when the number of bundles is $\mathrm{\ell }$. Then, we prove that the lemma holds when the number of bundles is $\mathrm{\ell }+1$. For the sake of contradiction, suppose that there exists an optimal coloring $c^{\ast }$ such that ${\max }_{v\in B}{c}^{\ast }(v)>\chi (G)(\mathrm{\ell }+1)$ for some $B\in ℬ$. Fix such a member $B$, and let $U$ be the set of vertices of $G$ that belong to $B$, but not to other bundles. Then, consider the instance $I^{\prime }=(G-U,ℬ\setminus \{B\},{w|}_{V\setminus U},C)$, where ${w|}_{V\setminus U}$ is the restriction of $w$ on $V\setminus U$. By the induction hypothesis, there exists an optimal coloring $c^{\prime }:V\setminus U\to {\mathbb{Z}}_{>0}$ for $I^{\prime }$ such that ${\max }_{v\in V\setminus U}{c}^{\prime }(v)\le \chi (G-U)\mathrm{\ell }\le \chi (G)\mathrm{\ell }$. We now extend $c^{\prime }$ to a coloring $c$ of $G$ by giving colors in $\{\chi (G)\mathrm{\ell }+1,\mathrm{\dots },\chi (G)\mathrm{\ell }+\chi (G)\}$ to the vertices of $U$. This is possible since $\chi (G[U])\le \chi (G)$. Then,

This contradicts the optimality of $c^{\ast }$. $◀$

We now focus on the case where the input graph $G$ has treewidth at most $𝗍𝗐$. Note that $\chi (G)\le 𝗍𝗐+1$, because the degeneracy of $G$ is at most $𝗍𝗐$. Thus, the number of colors in any optimal coloring is at most $(𝗍𝗐+1)|ℬ|$ by Lemma 4.

To solve Minimum Sum Coloring with Bundles for graphs $G=(V,E)$ with treewidth at most $𝗍𝗐$, we employ Courcelle’s theorem [1, 6, 7]. To this end, we introduce the following auxiliary decision problem. In addition to the input $(G,ℬ,w,C)$ to Minimum Sum Coloring with Bundles, where $ℬ=\{B_1,B_2,\mathrm{\dots },B_{\mathrm{\ell }}\}$, we also take a sequence $𝐤=(k_1,k_2,\mathrm{\dots },k_{\mathrm{\ell }})$ of integers. Then, we want to decide whether there exists a coloring $c:V\to {\mathbb{Z}}_{>0}$ such that ${\max }_{v\in B_j}c(v)\le k_j$ for all $j\in [\mathrm{\ell }]$. If we have a solution to this auxiliary problem for every $𝐤\in {[(𝗍𝗐+1)\mathrm{\ell }]}^{\mathrm{\ell }}$, then the optimal cost for the instance $(G,ℬ,w,C)$ can be derived as

We now focus on solving the auxiliary problem above. To solve the auxiliary problem using Courcelle’s theorem [1, 6, 7], it is sufficient to write down an MSO formula that expresses the decision. An instance is given as $(G,ℬ,w,C,𝐤)$, and we want to decide whether there exists a coloring $c$ such that ${\max }_{v\in B_j}c(v)\le k_j$ for all $j\in [\mathrm{\ell }]$. By Lemma 4, we can assume that our coloring $c$ uses colors in $[(𝗍𝗐+1)\mathrm{\ell }]$. For brevity, let $p=(𝗍𝗐+1)\mathrm{\ell }$. To express conditions with an MSO formula, we regard a coloring $c$ as a partition $\{C_1,C_2,\mathrm{\dots },C_p\}$ of the vertex set $V$ into independent sets, where $C_i=\{v\in V\mid c(v)=i\}$. Note that in such a partition a set $C_i$ can be empty.

Then, the decision can be expressed by the following MSO formula:

In the formula, the conjunction of Formulae (2) and (3) represents that $\{C_1,C_2,\mathrm{\dots },C_p\}$ is a partition of $V$. Formula (4) represents that each $C_i$ is independent. Formula (5) represents that the maximum color in bundle $B_j$ is at most $k_j$ for each $j\in [\mathrm{\ell }]$. Thus, the formula correctly represents the conditions in the auxiliary problem.

By Courcelle’s theorem, this auxiliary problem can be solved in $O(f(𝗍𝗐,\mathrm{\ell })|V|)$ time for some computable function $f$. To evaluate the minimum in (1), we solve the auxiliary problem for every choice of $𝐤\in {[(𝗍𝗐+1)\mathrm{\ell }]}^{\mathrm{\ell }}$, thus at most ${((𝗍𝗐+1)\mathrm{\ell })}^{\mathrm{\ell }}$ times. Let $g(𝗍𝗐)|V|$ be the running time of Bodlaender’s algorithm [4] for computing a tree decomposition of width $𝗍𝗐$. Then, the overall running time is $g(𝗍𝗐)|V|+{((𝗍𝗐+1)\mathrm{\ell })}^{\mathrm{\ell }}\cdot O(f(𝗍𝗐,\mathrm{\ell })|V|)$. Setting $h(𝗍𝗐,\mathrm{\ell })=g(𝗍𝗐)+{((𝗍𝗐+1)\mathrm{\ell })}^{\mathrm{\ell }}f(𝗍𝗐,\mathrm{\ell })$, we obtain the following theorem.

Let $t$ be the number of non-singleton bundles. Since $ℬ$ is a partition of $V$, we obtain $|V|\ge 2t+(|ℬ|-t)=|ℬ|+t$. Thus, $t\le |V|-|ℬ|$. $◀$

Let $I=(G=(V,E),ℬ,w,C)$ be an instance of Minimum Sum Coloring with Bundles, and assume that $G$ is a tree, $ℬ$ is a partition of $V$. Let $t$ be the number of non-singleton bundles in $ℬ$. By Lemma 6, $t\le |V|-|ℬ|=n-\mathrm{\ell }$. Denote the non-singleton bundles in $ℬ$ by $B_1,B_2,\mathrm{\dots },B_t$, and the set of vertices, each of which forms a singleton bundle, by $V_s$.

A primary idea of our algorithm is to fix upper bounds on the colors used in non-singleton bundles and to optimize the colors in singleton bundles with this restriction. For a non-singleton bundle $B_j$, $j\in [t]$, let $k_j$ be an upper bound on the colors in $B_j$; namely, we seek a coloring $c$ such that ${\max }_{u\in B_j}c(u)\le k_j$ for every $j\in [t]$. For brevity, we denote $𝐤=(k_1,k_2,\mathrm{\dots },k_t)$. By Lemma 4, it is enough to consider the situations with $k_j\le 2\mathrm{\ell }$ for all $j\in [t]$, and thus the number of possible choices for $𝐤$ is bounded by ${(2\mathrm{\ell })}^t$ from above.

We regard $G$ as a rooted tree with a root $r\in V$. For each vertex $v\in V$, we denote by $V(v)$ the vertex set of the subtree of $G$ rooted at $v$. For each vertex $v\in V$, each color $k$, and an upper-bound tuple $𝐤$, we define

Then, the optimal value for the instance $I$ is read by

where the minimum is taken over all possible choices of $𝐤=(k_1,k_2,\mathrm{\dots },k_t)$ and $k$. Note that we only need to consider the value of $k$ in the interval $k\in [2\mathrm{\ell }]$ by Lemma 4.

We now establish a recursive formula for $f(v,k;𝐤)$. First, consider the case where $v$ is a leaf of $G$. We have two subcases. If $v$ forms a singleton bundle by itself, then

If $v$ belongs to a non-singleton bundle $B_j$ for some $j\in [t]$, which is unique since $ℬ$ forms a partition of $V$, then

Next, consider the case where $v$ is not a leaf of $G$. Let $v_1,\mathrm{\dots },v_z$ be the children of $v$ in $G$. We again have two subcases. If $v$ forms a singleton bundle by itself, then

since the values $f(v_y,k_y^{\prime };𝐤)$ are independent from each other. Similarly, if $v$ belongs to a non-singleton bundle $B_j$ for some $j\in [t]$, then

For each fixed $𝐤$, we compute $f(v,k;𝐤)$ in a bottom-up manner from leaves to root. When $v$ is not a leaf, the computation of $f(v,k;𝐤)$ can be done in $O(z\mathrm{\ell })$ time for each fixed $k$ since we may suppose that $k_y^{\prime }\le 2\mathrm{\ell }$ by Lemma 4. In total, for each fixed $𝐤$, the computation of $f(v,k;𝐤)$ over all $v$ and $k$ can be done in $O(n{\mathrm{\ell }}^2)$ time. Hence, for varying $𝐤$, the running time of our algorithm is $O({(2\mathrm{\ell })}^{t}n{\mathrm{\ell }}^2)$. When $n-\mathrm{\ell }$ is a parameter, this is an XP algorithm since $t\le n-\mathrm{\ell }$ by Lemma 6.

We summarize our findings in the following theorem.