Decomposing a graph into subgraphs with small components

Edge coloring is the problem of assigning a color to each edge of a graph such that no two adjacent edges have the same color. Any edge coloring of a graph with maximum degree $\Delta$ requires at least $\Delta$ colors. Vizing’s theorem states that $\Delta+1$ colors suffice. The minimum number of colors in any edge coloring of a graph is its chromatic index. Deciding whether the chromatic index of a graph with maximum degree $\Delta$ is $\Delta$ or $\Delta+1$ is generally a hard computational problem, although a constructive proof of Vizing’s theorem [25] implies a polynomial-time approximation algorithm with additive error at most $1$. Holyer [15] proved that edge coloring cubic graphs with three colors, where $\Delta=3$, is already NP-complete. Extending this result, Leven and Galil [21] proved that edge coloring $\Delta$-regular graphs with $\Delta$ colors is NP-complete for any $\Delta\geq 3$. Cai and Ellis [3] further proved that edge coloring $\Delta$-regular line graphs of bipartite graphs with $\Delta$ colors is NP-complete for any odd $\Delta\geq 3$. On the other hand, it is known that $\Delta$ colors always suffice for edge coloring bipartite graphs; see [4, Proposition 18.1.3] for a simple proof. Moreover, edge coloring bipartite graphs (or bipartite multigraphs) admits an efficient polynomial-time exact algorithm, even when $\Delta$ is part of the input [6].

Define the component size of a graph as the maximum number of edges in any connected component of the graph. In this paper, we study the following problem that generalizes edge coloring:

We show that graph decomposition becomes hard, even in bipartite graphs, when the upper bound on the component size of the resulting subgraphs is relaxed from $1$ (as in edge coloring) to any fixed $c\geq 2$:

The arboricity of a graph is the minimum number of parts in an edge partition of the graph such that each part induces a forest [26]. The trees in the forests may be restricted to various subclasses of trees, leading to several related concepts of arboricity. For example, the linear arboricity (respectively, star arboricity) of a graph is the minimum number of parts in an edge partition of the graph such that each part induces a disjoint union of paths (respectively, stars). While the arboricity of any graph can be computed in polynomial time [11], the arboricities with various restrictions on the trees often turn out to be hard to compute [17]. Our proof of Theorem 1 shows that arboricity and star arboricity with bounded component size are also hard to compute:

The linear $c$-arboricity of a graph is the minimum number of parts in an edge partition of the graph into linear $c$-forests, i.e., disjoint unions of paths of length at most $c$ [1]. Note that linear $1$-arboricity is simply chromatic index. Thus the aforementioned results on edge coloring [15, 21, 3] imply that determining the linear $1$-arboricity of a graph is hard. Bermond, Fouquet, Habib, and Peroche [1] proved that deciding whether a cubic graph has linear $3$-arboricity at most $2$ is NP-complete, and conjectured that determining the linear $c$-arboricity of a graph is hard for all $c$. Since linear $2$-arboricity is equivalent to arboricity and star arboricity with component size at most $2$, the $c=2$ case of this conjecture is confirmed by our Corollary 1 and Corollary 2:

For two graphs $G$ and $H$, an $H$-decomposition of $G$ is an edge partition of $G$ into subgraphs isomorphic to $H$. For any fixed graph $H$, the problem of deciding whether an input graph $G$ admits an $H$-decomposition is NP-complete when $H$ has a component of at least three edges [7], and is polynomially solvable when every component of $H$ has at most two edges [2], in contrast to Corollary 3.

We established in Theorem 1 that $(k,c)$-Decomposition is NP-complete in bipartite graphs. It is natural to ask whether the problem remains hard in simpler graphs. Our next theorem characterizes the complexity of $(k,c)$-Decomposition in trees:

Theorem 2 implies that for any fixed $c$, $(k,c)$-Decomposition in trees can be solved in polynomial time. For the related arboricity problem of deciding whether a tree admits an edge partition into $k$ linear $c$-forests, Chang, Chen, Fu, and Huang [5] presented an algorithm that runs in polynomial time when $c$ is fixed.

The decision problem $(k,c)$-Decomposition may be extended to two different optimization problems:

Theorem 1 implies that Minimum-Color Decomposition for any fixed $c\geq 2$ and Minimum-Size Decomposition for any fixed $k\geq 2$ are APX-hard and inapproximable within a factor of $3/2$ in bipartite graphs. The previous results on edge coloring [15, 21, 3] imply that Minimum-Color Decomposition for $c=1$ is APX-hard and inapproximable within a factor of $4/3$ in general graphs. In the next two theorems, we show that both minimization problems can be approximated very well in trees:

Kleinberg, Motwani, Raghavan, and Venkatasubramanian [19] introduced $(k,c)$-Fragmented Coloring, the problem of vertex partitioning a graph into $k$ induced subgraphs such that the number of vertices in each component of each subgraph is at most $c$. Our problem $(k,c)$-Decomposition is equivalent to $(k,c)$-Fragmented Coloring in line graphs, since edge partitioning a graph $G$ is the same as vertex partitioning the line graph $L(G)$.

The problem $(k,c)$-Fragmented Coloring in general graphs is easily shown to be NP-hard for any $k\geq 2$ and $c\geq 2$, because the graph property of at most $c$ vertices in each component is additive and induced-hereditary, while vertex partitioning into fixed additive induced-hereditary properties is NP-hard in general [10], except the special case of bipartite testing, i.e., vertex partitioning into two independent sets. Also, the problem is trivial in bipartite graphs (and hence in trees), since every bipartite graph has a vertex partition into two induced subgraphs in which every component has only one vertex.

Our proofs of Theorem 2, Theorem 3, and Theorem 4 are based on a close relationship between $(k,c)$-Decomposition in trees and the classical problem of Bin Packing:

It is well-known that Bin Packing is strongly NP-hard [12], and hence Unary Bin Packing is NP-hard, when both $k$ and $c$ are part of the input. In terms of parameterized complexity, Jansen et al. [16] proved that Unary Bin Packing, even with the condition $\sum_{i=1}^{n}w_{i}=kc$, is already W[1]-hard with parameter $k$. In the following theorem, we obtain a fixed-parameter algorithm for Bin Packing with parameter $c$:

Hochbaum and Shmoys [13] introduced the notion of dual approximation algorithms that approximate the feasibility of a problem rather than its optimality. The existence of dual approximation algorithms for Bin Packing, similar to the one in the following theorem, are known [14, Sections 9.3.2.1 and 9.3.2.2]. We obtain a simple alternative via Theorem 5.

Throughout the paper, the size of a graph is the number of edges in it. We may refer to an edge partition of a graph into $k$ subgraphs and the corresponding $k$-color assignment to the edges interchangeably.

In this section we prove Theorem 1, Corollary 1, and Corollary 2. Fix any $k\geq 2$ and $c\geq 2$. The problem $(k,c)$-Decomposition and the related arboricity problems are clearly in NP. We prove their NP-hardness in bipartite graphs in the following.

In this section we prove Theorem 5 by obtaining a fixed-parameter algorithm for Bin Packing with parameter $c$.

Recall Definition 4 that the input to Bin Packing consists of $n$ items of integer weights $w_{i}$, $1\leq i\leq n$, and $k$ bins of integer capacity $c$. The problem has a solution only if $\max\{w_{i}\mid 1\leq i\leq n\}\leq c$ and $\sum_{i=1}^{n}w_{i}\leq kc$, which we assume. Let $N$ be the size of the problem instance encoded in binary. Then $N=\Theta(n+\sum_{i=1}^{n}\log w_{i}+\log k+\log c)$. In particular, we have $\log kc=O(N)$.

For $1\leq w\leq c$, let $a_{w}$ be the number of items with weight $w$. In $N^{O(1)}$ time, we can compute $a_{w}$ for all $w$. Then $\sum_{w=1}^{c}w\,a_{w}=\sum_{i=1}^{n}w_{i}\leq kc$. With the multiplicities $a_{w}$ for $1\leq w\leq c$, we no longer need $w_{i}$ for $1\leq i\leq n$. Henceforth, we work on the $c$ integers $a_{w}$ only. Without loss of generality, we increase $a_{1}$ until $\sum_{w=1}^{c}w\,a_{w}=kc$. Note that each $a_{w}$ has magnitude at most $kc$, where $\log kc=O(N)$. It remains to decide whether the items with multiplicities $a_{w}$ can be partitioned into $k$ subsets, each of total weight exactly $c$.

Consider the two vectors $\boldsymbol{w}=(1,2,\ldots,c)$ and $\boldsymbol{a}=(a_{1},a_{2},\ldots,a_{c})$ in $\mathbb{Z}_{\geq 0}^{c}$. Then the condition $\sum_{w=1}^{c}w\,a_{w}=kc$ becomes $\boldsymbol{w}\cdot\boldsymbol{a}=kc$. For $b\geq 0$, let

Then $\mathcal{P}_{c}$ is the set of vectors corresponding to all feasible patterns of item multiplicities for a single bin, and we can reformulate the problem as deciding whether there exists a multiset of vectors in $\mathcal{P}_{c}$ whose sum is $\boldsymbol{a}$.

Recall that the partition number $p(n)$ for $n\geq 0$ is the number of multisets of positive integers summing up to $n$. In particular, $p(0)=1$. Then, by definition, the size of $\mathcal{P}_{c}$ is exactly $p(c)$. Moreover, the size of $\mathcal{P}_{b}$ is at most $p(b)$ for all $b\geq 0$.

It is known that $p(n)=2^{O(\sqrt{n})}$ [22, Theorem 15.7]. Let $d(c)\geq 0$ be the smallest integer such that $2^{d}>\sum_{h=0}^{d}p(hc)$ for all $d>d(c)$. Since $\sum_{h=0}^{d}p(hc)=2^{O(\sqrt{dc})}$, we have $d(c)=O(c)$.

Let $\boldsymbol{v}_{i}$, $1\leq i\leq p(c)$, be the vectors in $\mathcal{P}_{c}$. For any index set $I\subseteq\{1,\ldots,p(c)\}$, the vector $\sum_{i\in I}\lambda_{i}\boldsymbol{v}_{i}$, where $\lambda_{i}\in\mathbb{Z}_{\geq 0}$ for all $i\in I$, is called an integer conical combination of vectors in $\mathcal{P}_{c}$. Consider the integer conical hull of $\mathcal{P}_{c}$ consisting of all integer conical combinations of vectors in $\mathcal{P}_{c}$:

We prove the following lemma using a common technique for Carathéodory bounds; see for example [8, Lemma 3].

If there is a multiset of vectors in $\mathcal{P}_{c}$ summing up to $\boldsymbol{a}$, then $\boldsymbol{a}$ is an integer conical combination of vectors in $\mathcal{P}_{c}$, and hence is included in $\mathrm{int.cone}(\mathcal{P}_{c})$, and hence by Lemma 3 can be represented as an integer conical combination of $d\leq d(c)$ distinct vectors in $\mathcal{P}_{c}$. Thus to decide whether there exists a multiset of vectors in $\mathcal{P}_{c}$ whose sum is $\boldsymbol{a}$, we can enumerate all subsets of $\{1,\ldots,p(c)\}$ of size $d\leq d(c)$, then for each subset $I$, check whether $\sum_{i\in I}\lambda_{i}\boldsymbol{v}_{i}=\boldsymbol{a}$ has a solution with $\lambda_{i}\in\mathbb{Z}_{\geq 0}$ for all $i\in I$.

The checking step reduces to an integer linear program, with $O(c)$ linear constraints on at most $d(c)=O(c)$ variables $\lambda_{i}$, and with integer coefficients at most $kc$, where $\log kc=O(N)$.

We now analyze the running time of our algorithm. Recall that converting the item weights $w_{i}$ to multiplicities $a_{w}$ takes $N^{O(1)}$ time. Finding the $p(c)$ vectors in $\mathcal{P}_{c}$, $\boldsymbol{v}_{i}$ for $1\leq i\leq p(c)$, takes $c^{O(c)}$ time. The number of subsets of $\{1,\ldots,p(c)\}$ of size $d\leq d(c)$ is at most $(p(c))^{d(c)}=(2^{O(\sqrt{c})})^{O(c)}=2^{O(c^{3/2})}$.

Solving an integer linear program with $n$ variables and $m$ constraints and with maximum coefficient $\Delta$ takes $n^{O(n)}m^{O(1)}(\log\Delta)^{O(1)}$ time¹¹1See discussion at https://cstheory.stackexchange.com/questions/16530 for more refined estimates. [20, 18]. In our setting, this is $(O(c))^{O(c)}(O(c))^{O(1)}(O(N))^{O(1)}=c^{O(c)}N^{O(1)}$.

Thus the total running time is $N^{O(1)}+c^{O(c)}+2^{O(c^{3/2})}\cdot c^{O(c)}N^{O(1)}$, which simplifies to $2^{O(c^{3/2})}N^{O(1)}$, since $c^{O(c)}=2^{O(c\log c)}$. This completes the proof of Theorem 5.

In this section we prove Theorem 6.

Fix any $0<\epsilon\leq 1$. Separate the $n$ items into two groups: small items of weight at most $\epsilon c$, and large items of weight greater than $\epsilon c$.

Let $c^{\prime}=\lfloor 2\epsilon^{-2}\rfloor$. Note that $c^{\prime}\cdot\epsilon^{2}c/2\leq c$. For each large item of weight $w_{i}>\epsilon c$, let $w^{\prime}_{i}$ be the largest integer such that $w^{\prime}_{i}\cdot\epsilon^{2}c/2\leq w_{i}$. Then $(w^{\prime}_{i}+1)\cdot\epsilon^{2}c/2>w_{i}$.

The algorithm works as follows. If the total weight of the $n$ items exceeds $kc$, then clearly the $n$ items cannot be packed into $k$ bins of capacity $c$, so return no. Otherwise, construct a set of scaled items including one item of weight $w^{\prime}_{i}$ for each large item of weight $w_{i}$. Use the fixed-parameter algorithm in Theorem 5 to decide whether the set of at most $n$ scaled items $w^{\prime}_{i}$ can be packed into $k$ scaled bins of capacity $c^{\prime}$, then return the answer accordingly.

With at most $n$ scaled items and capacity $c^{\prime}=O(\epsilon^{-2})$ for the $k$ scaled bins, it follows by Theorem 5 that the running time of our dual approximation algorithm is $2^{O(\epsilon^{-3})}N^{O(1)}$, where $N$ is the size of the problem instance encoded in binary. This completes the proof of Theorem 6.

In this section we prove Theorem 2. The problem $(k,c)$-Decomposition is clearly in NP. In the following, we prove that when both $k$ and $c$ are part of the input, $(k,c)$-Decomposition in trees is not only NP-hard but also W[1]-hard with parameter $k$, and is FPT with parameter $c$.

In this section we prove Theorem 3 and Theorem 4. Let $T$ be a tree with $n$ vertices, $n-1$ edges, and maximum degree $\Delta<n$, rooted at an arbitrary vertex of degree $1$.