3
$\begingroup$

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes.

Does this have a constant approximation? ($p,k$ and the graph are all part of the input)

$\endgroup$
7
  • 1
    $\begingroup$ This question could use more context. Is this NP-hard to solve exactly? Also, are p and k given as input, or are you asking about constant p and k? $\endgroup$
    – a3nm
    Jan 18 at 10:11
  • 1
    $\begingroup$ @a3nm. p,k are part of the input I don't know if the problem is NP hard. $\endgroup$
    – Hao S
    Jan 18 at 22:32
  • $\begingroup$ Thanks. Are the weights on vertices? on edges? $\endgroup$
    – a3nm
    Jan 19 at 8:26
  • 1
    $\begingroup$ Update: it seems to me like, in fact, the NP-hardness of such problems is shown in Section 2 of Dyer and Frieze, On the complexity of partitioning graphs into connected subgraphs, Discrete applied mathematics, 1985. sciencedirect.com/science/article/pii/0166218X85900083 $\endgroup$
    – a3nm
    Jan 24 at 20:48
  • 1
    $\begingroup$ @a3nm, Indeed, it looks like that reference shows NP-hardness even for any constant $k\ge 3$ or any constant $p\ge 2$. I wonder about approximation algorithms for the metric case (when the graph is complete w/ edge weights satisfying the triangle inequality). $\endgroup$
    – Neal Young
    Jan 24 at 21:50

2 Answers 2

2
+50
$\begingroup$
  1. There is no poly-time approximation algorithm for this problem unless P=NP.

  2. For the metric case (when the graph is complete and the edge weights satisfy the triangle inequality), there is a poly-time 4-approximation algorithm. [EDITED TO ADD THIS]

First we give the details of the hardness result. After that we describe the approximation algorithm.

Part 1 - Hardness Result

Consider the following "restricted" variant of OP's problem: given $(p,G)$ (as above, but ignoring the edge weights), determine whether $G$ contains a forest consisting of $p$ subtrees, each of size $k=|V|/p$. Call this problem RP. This is the problem of determining whether there is a feasible solution to OP's problem, regardless of cost.

Lemma 1. RP is NP-hard.

Before sketching the proof, note that the lemma implies that finding any feasible solution to OP's problem (independent of cost) is NP-hard, so there is no approximation algorithm (in the standard sense) unless P=NP.

Proof sketch. Reference [1] studies the EQUITABLE CONNECTED PARTITION problem (ECP), which for our purposes is convenient to define as follows: given an undirected unweighted graph $G=(V,E)$ and integer $p$, does the vertex set of $G$ have a partition into $p$ parts $P_1, P_2, \ldots, P_p$ such that each part $P_i$ is connected (that is, induces a connected subgraph of $G$), and has size either $k$ or $k-1$, where $k=\lceil |V|/p\rceil$?

Theorem 1 of reference [1] (cited below) shows that ECP is W[1]-hard. (This essentially means that it is as hard as k-CLIQUE.) This implies that ECP is NP-hard.

Furthermore, as observed in reference [2], the proof of Theorem 1 of [1] is by a reduction that produces ECP instances of a particular form. Namely, the number of vertices in $G$ is $kp$. (See the postscript below for further discussion of this.)

It follows that ECP remains NP-hard when restricted to such instances. But ECP restricted in this way is equivalent to the problem RP that we defined above. Indeed, given any partition of the vertex set into $p$ parts, each part is connected if and only if the subgraph induced by the part contains a spanning subtree, while each part has size $k$ or $k-1$ if and only if each part has size $k$. (Because the average part size is $|V|/p = k$, so no part can have size $k-1$.) $~~\Box$


[1] Enciso, R., Fellows, M.R., Guo, J., Kanj, I., Rosamond, F., Suchý, O. (2009). What Makes Equitable Connected Partition Easy. In: Chen, J., Fomin, F.V. (eds) Parameterized and Exact Computation. IWPEC 2009. Lecture Notes in Computer Science, vol 5917. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-11269-0_10

[2] Meeks, K., Skerman, F. The Parameterised Complexity of Computing the Maximum Modularity of a Graph. Algorithmica 82, 2174–2199 (2020). https://doi.org/10.1007/s00453-019-00649-7


Postscript. Here are some comments about our claim in the proof that the reduction in the proof of Theorem 1 of [1] produces a graph with $kp$ vertices. Verifying that by reading the proof seems tedious. If we don't trust that the construction as described gives a graph with $kp$ vertices, it seems easily verifiable that we can "fix" the construction to ensure this as follows.

The following property is stated clearly in their proof: their construction builds into the graph $G$ "anchor" vertices $a_1, a_2, \ldots, a_p$ such that any good partition must have exactly one of these anchor vertices in each of its $p$ parts. It ensures this by attaching to each anchor vertex $a_i$ a large number, say, more than $k/2$ of pending vertices (vertices of degree 1). Because each part is connected and $k>1$, each pending vertex must end up in the same part as its anchor. No part can contain more than one anchor (as the part has size $k$ but must contain its anchors' pending vertices). Then, there are $p$ anchors and $p$ parts, so each part must contain exactly one anchor.

Informally, we would like to build a new graph $G'$ by adding $d$ new vertices to $G$, along with some edges to these vertices, so that given any "good" partition of $G$, we can obtain a good partition of $G'$ by adding one of the $d$ new vertices to each of those $d$ parts that have size $k-1$. However we have to be careful, we want to make sure that, conversely, each good partition in $G'$ still corresponds to some good partition in $G$. A first attempt would be to simply add $d$ new vertices, each of which has edges to all of the anchors $a_1, \ldots, a_p$. Then good partitions in $G$ would yield good partitions in $G'$. However, the converse could fail: in a good partition of $G'$, it could be, for example, that one part contains all $d$ of the new vertices.

To work around this, let $p' = p+1$, let $k' = 1 + 2\max(k, p-d)$. Add one new "anchor" vertex $a_{p'}$. For each old anchor vertex $a_i$ ($1\le i \le p$), create a new "bridge" vertex $b_i$ with edges $(a_i, b_i)$ and $(b_i, a_{p'})$, then add $k' - k$ new pending vertices, each of which is a new vertex whose only edge is to the bridge's anchor $a_i$. Finally, to the new anchor vertex $a_{p'}$, attach $k' - (p - d)$ new pending vertices (each with just one edge, to $a_{p'}$). This defines $G'$.

Define a "good" partition of $G'$ to be one that partitions the vertex set of $G'$ into $p'$ connected parts, each of size $k'$.

To finish we argue that the reduction is correct. First suppose there is a good partition of $G$. We argue that there must be a good partition of $G'$. The good partition of $G$ has $p$ connected parts, $d$ of which have size $k-1$, and $p-d$ of which have size $k$. Create the "good" partition of $G'$ as follows. For each of the $p$ parts of the good partition of $G$, recall that the part must contain exactly one anchor $a_i$ ($i\le p$). If the part has size $k-1$, add the bridge vertex $b_i$. In any case, also add the $k'-k$ new pending vertices of $a_i$. This brings the number of vertices in the part to $k'$. The modified part is connected because the original part was, and the anchor $a_i$ has edges to all of the new vertices added to the part. Finally, create a new part consisting of the new anchor $a_{p'}$, its $k' - (p-d)$ pending vertices, and the $d$ bridge vertices that were not yet added to any part. Now we have $p+1=p'$ connected parts of size $k'$, as desired.

Conversely suppose that there is a good partition of $G'$. Note that in $G'$ each anchor (including $a_{p'}$) is attached to at least $\min(k'-k, k'-(p-d)) > k'/2$ pending vertices. Each pending vertex must be in the same part as its anchor. It follows that each of the $p'=p+1$ parts of $G'$ contains exactly one distinct anchor (and the anchor's pending vertices).

First, from each part that contains an anchor $a_i$ other than $a_{p'}$, remove the $k'-k$ new pending vertices attached to $a_i$. This leaves the part with $k$ (connected) vertices including $a_i$. The part cannot contain any new vertex (in $G'$ but not $G$) other than $b_j$, because every path from $a_i$ to any such vertex goes through some anchor vertex other than $a_i$ (which is not in the part). Similarly, the part that contains $a_{p'}$ cannot contain any vertex from $G$, because each path from $a_{p'}$ into $G$ goes through some other anchor vertex $a_i \ne a_{p'}$. So removing the part containing $a_{p'}$ and removing the bridge vertex (if present) from each remaining part yields a good partition of $G$.


[EDITED TO ADD THIS SECTION.]

Part 2 - Approximation Algorithm

Lemma 2. There is a poly-time $4(1-1/k)$-approximation algorithm for the problem restricted to metric graphs.

Proof sketch. The algorithm proceeds in two stages. First, it uses an existing approximation algorithm for network design (e.g. reference [3] below) to compute a 2-approximate solution $X$ to a relaxation of the problem. It then modifies $X$, increasing its cost by a factor of at most $2(1-1/k)$, to obtain a true feasible solution $X'$ of cost at most $4(1-1/k)$ times the optimal.

Stage 1 -- computing the relaxed solution $X$.

Consider the following relaxation of the problem. Let $r:2^{V} \rightarrow \{0,1\}$ be defined by $$r(S) = \begin{cases} 0 & \textit{if } |S| \bmod k = 0 \\ 1 & \textit{otherwise.} \end{cases}$$ The relaxed problem is to find a min-cost set $X$ of edges such that the number of edges in $X$ crossing any cut $(S, V\setminus S)$ is at least $r(S)$.

Using that $|V| \bmod k = 0$, any set $X$ of edges corresponding to a solution to OP's problem satisfies this constraint, so indeed this relaxed problem is a relaxation of OP's problem.

Note that $r$ is proper (that is, per [3], that $r(A) = r(B) = 0 \implies r(A \cup B) = 0$ for any two disjoint $A,B\subseteq V$). Also, given any set $S\subseteq V$, one can compute $r(S)$ in poly time. It follows from the general result in [3] that one can compute a 2-approximate solution $X$ to the relaxation in poly time. Doing this is the first stage of the algorithm.

Stage 2 -- converting $X$ to the true feasible solution $X'$.

Consider the subgraph $G_X = (V, X)$. For each connected component $C$ of $G_X$, do the following. Note that by the definition of $f$, the size of the vertex set $V(C)$ of $C$ is a multiple of $k$. Assume WLOG that $X$ is a minimal solution to the relaxation, so that $C$ is a spanning tree of $V(C)$. Using the standard trick of walking around the spanning tree and shortcutting, convert $C$ into a cycle $C'$ that visits each vertex in $V(C)$ exactly once and has total edge weight at most twice that of $C$ (using here that the graph is metric).

Recalling that $|V(C)|$ is a multiple of $k$, break the cycle $C'$ into a set $P_C$ of paths of length $k-1$ (edges) by starting at a random starting point on the cycle and then removing every $k$th edge. The expected total edge weight of the edges in $P_C$ is $(1-1/k)$ times the weight of edges in $C'$, which is at most $2(1-1/k)$ times the weight of edges in $C$.

Take the final solution $X'$ to be the union, over all the components $C$ in $G_X$, of the edge set $P_C$ computed as above for $C$. In expectation, the cost of $X'$ is at most $2(1-1/k)$ times the cost of the relaxed solution $X$. Because the cost of $X$ is at most twice the cost of the optimal relaxed cost, and the optimal relaxed cost is at most the optimal cost for the original instance, the expected cost of $X'$ is at most $4(1-1/k)$ times optimal.

The algorithm can be derandomized simply by choosing the best of the $k$ choices for each component $C$. $~~~~\Box$


[3] Goemans, M. X., et al. "Improved approximation algorithms for network design problems." Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms. 1994.

$\endgroup$
1
$\begingroup$

I think I can show that the problem is NP-hard, even in the case where the graph is unweighted. Specifically, given an undirected graph $G$, and values $p$ and $k$, I want to know if I can partition the vertex set of $G$ into $p$ subsets that each contain exactly $k$ vertices, such that the induced subgraph on these $k$ vertices is connected. (This is equivalent to saying that these $k$ vertices in $G$ are connected by a tree of edges of $G$; and then all solutions have the same weight, namely, $p (k-1)$.)

(Remark: In case you were thinking of a setting where we have a complete graph on $N$ vertices and we want to give a weight to each possible edge $\{i, j\}$, then you can simply take an unweighted graph $G$ in my sense and convert it to a complete graph $G'$ where you give weight $1$ to the edges of $G$ and weight $N$ to the non-edges of $G$. Then, we ask whether there is a choice of $p$ trees of exactly $k$ vertices in $G'$ that has total weight $p (k-1) < N$. This is possible only if we do not use a non-edge of $G$.)

I show NP-hardness by reducing from unary-3-partition. An instance $I$ to unary-3-partition consists of integers $n_1, ..., n_{3k}$ written in unary, and a number $t$. The unary-3-partition problem asks whether the numbers can be partitioned into $k$ triples that all have the same sum $t$.

Let me first describe the reduction. Given a unary-3-partition instance $I$, letting $M$ be the maximum number in $I$, we define $B := 3M+1$. Now, construct a graph G_I where each number $n_i$ is represented as a chain of $B+i$ vertices (called a "number chain"), and where we further have $k$ disjoint chains each having $4B$ vertices (called "triple chains"). Further, there are $(3 k) \times k$ edges (called "connection edges"), each of which connects the first vertex of a number chain to the first vertex of a triple chain. (Hence, in every chain, we have the following property (*): only the first vertex is connected to vertices outside the chain.) We ask if the graph $G_I$ can be partitioned in $k$ components each containing exactly $7B+t$ nodes. This reduction is in polynomial time, remembering that the numbers of $I$ are written in unary.

One direction of the correctness proof is trivial: if the unary-3-partition instance $I$ has a solution $(r_1, s_1, t_1), ..., (r_k, s_k, t_k)$, then we partition the graph $G_I$ into $k$ components in the following way. The $i$-th component consists of the vertices of the $i$-th triple chain and of the three numbers $r_i s_i t_i$ that are in this triple according to the solution; note that the three number chains are connected to the triple chain by the connection edges). Then the component contains $4B+3B+t = 7B+t$ vertices, because we know that $r_i+s_i+t_i = t$.

For the converse direction, let us assume that $G_I$ can be partitioned into $k$ components each having exactly $7B+t$ vertices. Observe that for every chain (number-chain or triple-chain), it must be the case that all vertices of the chain are in the same component. Indeed, if this were not the case, then considering the component that contains the last vertex of the chain, as this component is connected and does not contain the first vertex of the chain, then by property (*) it must be a strict subset of the chain, so it must contain strictly less than $B+M$ vertices (for number chains) or less than $4B$ vertices (for triple chains), in any case it would contain less than $7B+t$ vertices. Thus, each of the $k$ components of $G_I$ must consist of a subset of (complete) chains.

Now, a component cannot contain two triple chains, because it would then contain at least $8B$ vertices, and $8B>7B+t$ because $t \leq 3M < B$, contradicting the requirementh that the component contains $7B+t$ vertices. For this reason, as we have $k$ components, by the pigeonhole principle it must be the case that each component contains exactly one triple chain. This implies that the number chains must be partitioned across the components and each component contains number chains summing to $3B+t$, so that the total size is $3B+t+4B = 7B+t$.

Now, we claim that each component must consist of exactly 3 number chains. Indeed, if a component contains two number chains or less then these number chains sum to at most $2B+2M < 3B < 3B+t$. Thus, by the pigeonhole principle again, no component can contain more than 3 number chains (otherwise some other component must have less). Thus, each component must consist of exactly 3 number chains. Now, as the remaining number of vertices per component was $3B+t$, we see that the numbers of these 3 chains must sum to exactly $t$. This concludes the reduction.

I believe this NP-hardness proof shows that the problem considered in the question is hard to approximate within any constant factor. Indeed, let us assume there is a constant $c$ to which we can approximate the problem. Perform the reduction above from UNARY-3-PARTITION but multiplying every number by the constant $c$. In the resulting instance, the same reasoning should show that any solution on $G_I$ that is correct within a multiplicative factor of $c$ must in fact be an exact solution (because all numbers are multiples of $c$), and so I had a solution. (A similar reasoning is used in this paper to show inapproximability)

$\endgroup$
1
  • $\begingroup$ I should clarify that I wrote posted this proof independently from @NealYoung's answer. To comment on the relationship between the two: it looks like we agree on the outcome (inapproximability), my answer gives a self-contained reduction from unary-3-partition, Neal's builds on a reference showing hardness of a related problem studied in an existing paper. Both my proof and the one in the paper seem to be using similar ideas. Congrats in any case to Neal for being faster than me. ;) $\endgroup$
    – a3nm
    Jan 24 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.