<ol>
<li><p>There is no poly-time approximation algorithm for this problem unless P=NP.</p>
</li>
<li><p>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]</p>
</li>
</ol>
<p>First we give the details of the hardness result.  After that we describe the approximation algorithm.</p>
<h1>Part 1 - Hardness Result</h1>
<p>Consider the following &quot;restricted&quot; variant of OP's problem: <em>given <span class="math-container">$(p,G)$</span> (as above, but ignoring the edge weights), determine whether <span class="math-container">$G$</span> contains a forest consisting of <span class="math-container">$p$</span> subtrees, each of size <span class="math-container">$k=|V|/p$</span>.</em>  Call this problem RP.  This is the problem of determining whether there is a feasible solution to OP's problem, regardless of cost.</p>
<p><strong>Lemma 1.</strong> <em>RP is NP-hard.</em></p>
<p>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.</p>
<p><em>Proof sketch.</em>  Reference [1] studies the EQUITABLE CONNECTED PARTITION problem (ECP), which for our purposes is convenient to define as follows: <em>given an undirected unweighted graph <span class="math-container">$G=(V,E)$</span> and integer <span class="math-container">$p$</span>, does the vertex set of <span class="math-container">$G$</span> have a partition into <span class="math-container">$p$</span> parts <span class="math-container">$P_1, P_2, \ldots, P_p$</span> such that each part <span class="math-container">$P_i$</span> is connected (that is, induces a connected subgraph of <span class="math-container">$G$</span>), and has size either <span class="math-container">$k$</span> or <span class="math-container">$k-1$</span>, where <span class="math-container">$k=\lceil |V|/p\rceil$</span>?</em></p>
<p>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.</p>
<p>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, <em>the number of vertices in <span class="math-container">$G$</span> is <span class="math-container">$kp$</span></em>.  (See the postscript below for further discussion of this.)</p>
<p>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 <span class="math-container">$p$</span> parts, each part is connected if and only if the subgraph induced by the part contains a spanning subtree, while each part has size <span class="math-container">$k$</span> or <span class="math-container">$k-1$</span> if and only if each part has size <span class="math-container">$k$</span>.  (Because the average part size is <span class="math-container">$|V|/p = k$</span>, so no part can have size <span class="math-container">$k-1$</span>.)  <span class="math-container">$~~\Box$</span></p>
<hr />
<p>[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. <a href="https://doi.org/10.1007/978-3-642-11269-0_10" rel="nofollow noreferrer">https://doi.org/10.1007/978-3-642-11269-0_10</a></p>
<p>[2] Meeks, K., Skerman, F. The Parameterised Complexity of Computing the Maximum Modularity of a Graph. Algorithmica 82, 2174–2199 (2020). <a href="https://doi.org/10.1007/s00453-019-00649-7" rel="nofollow noreferrer">https://doi.org/10.1007/s00453-019-00649-7</a></p>
<hr />
<p><strong>Postscript.</strong> 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 <span class="math-container">$kp$</span> vertices.  Verifying that by reading the proof seems tedious.   If we don't trust that the construction as described gives a graph with <span class="math-container">$kp$</span> vertices, it seems easily verifiable that we can &quot;fix&quot; the construction to ensure this as follows.</p>
<p>The following property is stated clearly in their proof: their construction builds into the graph <span class="math-container">$G$</span> &quot;anchor&quot; vertices <span class="math-container">$a_1, a_2, \ldots, a_p$</span> such that any good partition must have exactly one of these anchor vertices in each of its <span class="math-container">$p$</span> parts.  It ensures this by attaching to each anchor vertex <span class="math-container">$a_i$</span> a large number, say, more than <span class="math-container">$k/2$</span> of <em>pending</em> vertices (vertices of degree 1).  Because each part is connected and <span class="math-container">$k&gt;1$</span>, 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 <span class="math-container">$k$</span> but must contain its anchors' pending vertices).  Then, there are <span class="math-container">$p$</span> anchors and <span class="math-container">$p$</span> parts, so each part must contain exactly one anchor.</p>
<p>Informally, we would like to build a new graph <span class="math-container">$G'$</span> by adding <span class="math-container">$d$</span> new vertices to <span class="math-container">$G$</span>, along with some edges to these vertices, so that given any &quot;good&quot; partition of <span class="math-container">$G$</span>, we can obtain a good partition of <span class="math-container">$G'$</span> by adding one of the <span class="math-container">$d$</span> new vertices to each of those <span class="math-container">$d$</span> parts that have size <span class="math-container">$k-1$</span>.  However we have to be careful, we want to make sure that, conversely, each good partition in <span class="math-container">$G'$</span> still corresponds to some good partition in <span class="math-container">$G$</span>.  A first attempt would be to simply add <span class="math-container">$d$</span> new vertices, each of which has edges to all of the anchors <span class="math-container">$a_1, \ldots, a_p$</span>.  Then good partitions in <span class="math-container">$G$</span> would yield good partitions in <span class="math-container">$G'$</span>.  However, the converse could fail: in a good partition of <span class="math-container">$G'$</span>, it could be, for example, that one part contains all <span class="math-container">$d$</span> of the new vertices.</p>
<p>To work around this, let <span class="math-container">$p' = p+1$</span>, let <span class="math-container">$k' = 1 + 2\max(k, p-d)$</span>.
Add one new &quot;anchor&quot; vertex <span class="math-container">$a_{p'}$</span>.
For each old anchor vertex <span class="math-container">$a_i$</span> (<span class="math-container">$1\le i \le p$</span>),
create a new &quot;bridge&quot; vertex <span class="math-container">$b_i$</span> with edges <span class="math-container">$(a_i, b_i)$</span> and <span class="math-container">$(b_i, a_{p'})$</span>,
then add <span class="math-container">$k' - k$</span> new pending vertices, each of which is a new vertex whose only edge is to the bridge's anchor <span class="math-container">$a_i$</span>.
Finally, to the new anchor vertex <span class="math-container">$a_{p'}$</span>,
attach <span class="math-container">$k' - (p - d)$</span> new pending vertices
(each with just one edge, to <span class="math-container">$a_{p'}$</span>).
This defines <span class="math-container">$G'$</span>.</p>
<p>Define a &quot;good&quot; partition of <span class="math-container">$G'$</span> to be one that partitions the vertex set of <span class="math-container">$G'$</span> into <span class="math-container">$p'$</span> connected parts, each of size <span class="math-container">$k'$</span>.</p>
<p>To finish we argue that the reduction is correct.
First suppose there is a good partition of <span class="math-container">$G$</span>.
We argue that there must be a good partition of <span class="math-container">$G'$</span>.
The good partition of <span class="math-container">$G$</span> has <span class="math-container">$p$</span> connected parts, <span class="math-container">$d$</span> of which have size <span class="math-container">$k-1$</span>, and <span class="math-container">$p-d$</span> of which have size <span class="math-container">$k$</span>.  Create the &quot;good&quot; partition of <span class="math-container">$G'$</span> as follows.  For each of the <span class="math-container">$p$</span> parts of the good partition of <span class="math-container">$G$</span>, recall that the part must contain exactly one anchor <span class="math-container">$a_i$</span> (<span class="math-container">$i\le p$</span>).
If the part has size <span class="math-container">$k-1$</span>, add the bridge vertex <span class="math-container">$b_i$</span>.
In any case, also add the <span class="math-container">$k'-k$</span> new pending vertices of <span class="math-container">$a_i$</span>.
This brings the number of vertices in the part to <span class="math-container">$k'$</span>.
The modified part is connected because the original part was, and the anchor <span class="math-container">$a_i$</span> has edges to all of the new vertices added to the part.
Finally, create a new part consisting of the new anchor <span class="math-container">$a_{p'}$</span>, its <span class="math-container">$k' - (p-d)$</span> pending vertices, and the <span class="math-container">$d$</span> bridge vertices that were not yet added to any part.  Now we have <span class="math-container">$p+1=p'$</span> connected parts of size <span class="math-container">$k'$</span>, as desired.</p>
<p>Conversely suppose that there is a good partition of <span class="math-container">$G'$</span>.
Note that in <span class="math-container">$G'$</span> each anchor (including <span class="math-container">$a_{p'}$</span>) is attached to at least <span class="math-container">$\min(k'-k, k'-(p-d)) &gt; k'/2$</span> pending vertices.  Each pending vertex must be in the same part as its anchor.  It follows that each of the <span class="math-container">$p'=p+1$</span> parts of <span class="math-container">$G'$</span> contains exactly one distinct anchor (and the anchor's pending vertices).</p>
<p>First, from each part that contains an anchor <span class="math-container">$a_i$</span> other than <span class="math-container">$a_{p'}$</span>, remove the <span class="math-container">$k'-k$</span> new pending vertices attached to <span class="math-container">$a_i$</span>.  This leaves the part with <span class="math-container">$k$</span> (connected) vertices including <span class="math-container">$a_i$</span>.  The part cannot contain any new vertex (in <span class="math-container">$G'$</span> but not <span class="math-container">$G$</span>) other than <span class="math-container">$b_j$</span>, because every path from <span class="math-container">$a_i$</span> to any such vertex goes through some anchor vertex other than <span class="math-container">$a_i$</span> (which is not in the part).
Similarly, the part that contains <span class="math-container">$a_{p'}$</span> cannot contain any vertex from <span class="math-container">$G$</span>, because each path from <span class="math-container">$a_{p'}$</span> into <span class="math-container">$G$</span> goes through some other anchor vertex <span class="math-container">$a_i \ne a_{p'}$</span>.
So removing the part containing <span class="math-container">$a_{p'}$</span>
and removing the bridge vertex (if present) from each remaining part yields a good partition of <span class="math-container">$G$</span>.</p>
<hr />
<p>[EDITED TO ADD THIS SECTION.]</p>
<h1>Part 2 - Approximation Algorithm</h1>
<p><strong>Lemma 2.</strong> <em>There is a poly-time <span class="math-container">$4(1-1/k)$</span>-approximation algorithm for the problem restricted to metric graphs.</em></p>
<p><em>Proof sketch.</em> 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 <span class="math-container">$X$</span> to a relaxation of the problem.  It then modifies <span class="math-container">$X$</span>, increasing its cost by a factor of at most <span class="math-container">$2(1-1/k)$</span>, to obtain a true feasible solution <span class="math-container">$X'$</span> of cost at most <span class="math-container">$4(1-1/k)$</span> times the optimal.</p>
<p><em>Stage 1 -- computing the relaxed solution <span class="math-container">$X$</span>.</em></p>
<p>Consider the following relaxation of the problem.  Let <span class="math-container">$r:2^{V} \rightarrow \{0,1\}$</span> be defined by
<span class="math-container">$$r(S) = \begin{cases}
0 &amp; \textit{if } |S| \bmod k = 0 \\
1 &amp; \textit{otherwise.}
\end{cases}$$</span>
The relaxed problem is to find a min-cost set <span class="math-container">$X$</span> of edges such that the number of edges in <span class="math-container">$X$</span> crossing any cut <span class="math-container">$(S, V\setminus S)$</span> is at least <span class="math-container">$r(S)$</span>.</p>
<p>Using that <span class="math-container">$|V| \bmod k = 0$</span>, any set <span class="math-container">$X$</span> 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.</p>
<p>Note that <span class="math-container">$r$</span> is <em>proper</em> (that is, per [3], that <span class="math-container">$r(A) = r(B) = 0 \implies r(A \cup B) = 0$</span> for any two disjoint <span class="math-container">$A,B\subseteq V$</span>).  Also, given any set <span class="math-container">$S\subseteq V$</span>, one can compute <span class="math-container">$r(S)$</span> in poly time.  It follows from the general result in [3] that one can compute a 2-approximate solution <span class="math-container">$X$</span> to the relaxation in poly time.  Doing this is the first stage of the algorithm.</p>
<p><em>Stage 2 -- converting <span class="math-container">$X$</span> to the true feasible solution <span class="math-container">$X'$</span>.</em></p>
<p>Consider the subgraph <span class="math-container">$G_X = (V, X)$</span>.  For each connected component <span class="math-container">$C$</span> of <span class="math-container">$G_X$</span>, do the following.  Note that by the definition of <span class="math-container">$f$</span>, the size of the vertex set <span class="math-container">$V(C)$</span> of <span class="math-container">$C$</span> is a multiple of <span class="math-container">$k$</span>.  Assume WLOG that <span class="math-container">$X$</span> is a minimal solution to the relaxation, so that <span class="math-container">$C$</span> is a spanning tree of <span class="math-container">$V(C)$</span>.  Using the standard trick of walking around the spanning tree and shortcutting, convert <span class="math-container">$C$</span> into a cycle <span class="math-container">$C'$</span> that visits each vertex in <span class="math-container">$V(C)$</span> exactly once and has total edge weight at most twice that of <span class="math-container">$C$</span> (using here that the graph is metric).</p>
<p>Recalling that <span class="math-container">$|V(C)|$</span> is a multiple of <span class="math-container">$k$</span>, break the cycle <span class="math-container">$C'$</span> into a set <span class="math-container">$P_C$</span> of paths of length <span class="math-container">$k-1$</span> (edges) by starting at a random starting point on the cycle and then removing every <span class="math-container">$k$</span>th edge.  The expected total edge weight of the edges in <span class="math-container">$P_C$</span> is <span class="math-container">$(1-1/k)$</span> times the weight of edges in <span class="math-container">$C'$</span>, which is at most <span class="math-container">$2(1-1/k)$</span> times the weight of edges in <span class="math-container">$C$</span>.</p>
<p>Take the final solution <span class="math-container">$X'$</span> to be the union, over all the components <span class="math-container">$C$</span> in <span class="math-container">$G_X$</span>, of the edge set <span class="math-container">$P_C$</span> computed as above for <span class="math-container">$C$</span>.  In expectation, the cost of <span class="math-container">$X'$</span> is at most <span class="math-container">$2(1-1/k)$</span> times the cost of the relaxed solution <span class="math-container">$X$</span>.  Because the cost of <span class="math-container">$X$</span> 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 <span class="math-container">$X'$</span> is at most <span class="math-container">$4(1-1/k)$</span> times optimal.</p>
<p>The algorithm can be derandomized simply by choosing the best of the <span class="math-container">$k$</span> choices for each component <span class="math-container">$C$</span>.  <span class="math-container">$~~~~\Box$</span></p>
<hr />
<p>[3] Goemans, M. X., et al. &quot;Improved approximation algorithms for network design problems.&quot; Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms. 1994.</p>

CC BY-SA 4.0
2024-01-24T19:29:02.910Z
2024-01-25T01:15:54.933Z
2024-01-25T01:15:54.933Z
Neal Young
<p>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 <span class="math-container">$G$</span>, and
values <span class="math-container">$p$</span> and <span class="math-container">$k$</span>, I want to know if I can partition the vertex set of <span class="math-container">$G$</span> into
<span class="math-container">$p$</span>
subsets that each contain exactly <span class="math-container">$k$</span> vertices, such that the induced subgraph on
these <span class="math-container">$k$</span> vertices is connected. (This is equivalent to saying that these <span class="math-container">$k$</span>
vertices in <span class="math-container">$G$</span> are connected by a tree of edges of <span class="math-container">$G$</span>; and then all solutions
have the same weight, namely, <span class="math-container">$p (k-1)$</span>.)</p>
<p>(<strong>Remark:</strong> In case you were thinking of a setting where we have a complete graph on <span class="math-container">$N$</span>
vertices and we want to give a weight to each possible edge <span class="math-container">$\{i, j\}$</span>, then you can
simply take an unweighted graph <span class="math-container">$G$</span> in my sense and convert it to a complete graph
<span class="math-container">$G'$</span>
where you give
weight <span class="math-container">$1$</span> to the edges of <span class="math-container">$G$</span> and weight <span class="math-container">$N$</span> to the non-edges of <span class="math-container">$G$</span>. Then, we
ask whether there is a
choice of <span class="math-container">$p$</span>
trees of exactly <span class="math-container">$k$</span> vertices in <span class="math-container">$G'$</span> that has total weight <span class="math-container">$p (k-1) &lt; N$</span>. This is
possible only if we do not use a non-edge of <span class="math-container">$G$</span>.)</p>
<p>I show NP-hardness by reducing from unary-3-partition. An instance <span class="math-container">$I$</span> to
unary-3-partition consists
of integers <span class="math-container">$n_1, ..., n_{3k}$</span> written in unary, and a number <span class="math-container">$t$</span>. The unary-3-partition problem asks whether the
numbers can be
partitioned into <span class="math-container">$k$</span> triples that all have the same sum <span class="math-container">$t$</span>.</p>
<p>Let me first describe the reduction. Given a unary-3-partition instance <span class="math-container">$I$</span>,
letting <span class="math-container">$M$</span> be the maximum number in <span class="math-container">$I$</span>, we define <span class="math-container">$B := 3M+1$</span>.
Now, construct a graph G_I where each number <span class="math-container">$n_i$</span> is
represented as a chain of <span class="math-container">$B+i$</span> vertices (called a &quot;number chain&quot;), and where we
further have <span class="math-container">$k$</span> disjoint chains each
having <span class="math-container">$4B$</span> vertices (called &quot;triple chains&quot;). Further, there are <span class="math-container">$(3 k) \times
k$</span> edges (called &quot;connection edges&quot;), 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 <span class="math-container">$G_I$</span> can be partitioned in <span class="math-container">$k$</span> components each containing
exactly <span class="math-container">$7B+t$</span> nodes.
This reduction is in polynomial time, remembering that the numbers of <span class="math-container">$I$</span> are written
in unary.</p>
<p>One direction of the correctness proof is trivial: if the unary-3-partition
instance <span class="math-container">$I$</span> has a solution <span class="math-container">$(r_1, s_1, t_1), ..., (r_k, s_k, t_k)$</span>, then we
partition the graph <span class="math-container">$G_I$</span> into <span class="math-container">$k$</span>
components in the following way. The <span class="math-container">$i$</span>-th component consists of the
vertices of the <span class="math-container">$i$</span>-th
triple chain and of the three numbers <span class="math-container">$r_i s_i t_i$</span> 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 <span class="math-container">$4B+3B+t = 7B+t$</span> vertices, because we know that <span class="math-container">$r_i+s_i+t_i = t$</span>.</p>
<p>For the converse direction, let us assume that <span class="math-container">$G_I$</span> can be partitioned into <span class="math-container">$k$</span>
components each having exactly <span class="math-container">$7B+t$</span> 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 <span class="math-container">$B+M$</span> vertices (for number chains) or less
than <span class="math-container">$4B$</span> vertices (for triple
chains), in any case it would contain less than <span class="math-container">$7B+t$</span> vertices.
Thus, each of the <span class="math-container">$k$</span> components of <span class="math-container">$G_I$</span> must consist of a subset of (complete)
chains.</p>
<p>Now, a component cannot contain two triple chains, because it would then
contain at least <span class="math-container">$8B$</span> vertices, and <span class="math-container">$8B&gt;7B+t$</span> because <span class="math-container">$t \leq 3M &lt; B$</span>,
contradicting the requirementh that the component contains <span class="math-container">$7B+t$</span> vertices. For
this reason, as we have <span class="math-container">$k$</span> 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 <span class="math-container">$3B+t$</span>, so that the total size is
<span class="math-container">$3B+t+4B = 7B+t$</span>.</p>
<p>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
<span class="math-container">$2B+2M &lt; 3B &lt; 3B+t$</span>. 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 <span class="math-container">$3B+t$</span>, we see that
the numbers of these 3 chains must sum to exactly <span class="math-container">$t$</span>. This concludes the reduction.</p>
<p>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 <span class="math-container">$c$</span> to which we can approximate the problem. Perform
the reduction above from UNARY-3-PARTITION but multiplying every number by the
constant <span class="math-container">$c$</span>. In the resulting instance, the same reasoning should show that any
solution on <span class="math-container">$G_I$</span> that is correct within a multiplicative factor of <span class="math-container">$c$</span> must in fact
be an exact solution (because all numbers are multiples of <span class="math-container">$c$</span>), and so I had a
solution. (A similar reasoning is used in <a href="https://arxiv.org/abs/cs/0210020" rel="nofollow noreferrer">this
paper</a> to show inapproximability)</p>

CC BY-SA 4.0
2024-01-24T20:16:08.563Z
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. ;)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-24T20:06:12.177Z
2024-01-24T20:06:12.177Z
Antoine Amarilli 'a3nm'
<p>Given a weighted graph with <span class="math-container">$pk$</span> nodes find a min weight forest with <span class="math-container">$p$</span> components each containing exactly <span class="math-container">$k$</span> nodes.</p>
<p>Does this have a constant approximation?
(<span class="math-container">$p,k$</span> and the graph are all part of the input)</p>

CC BY-SA 4.0
2024-01-18T10:11:02.370Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-18T22:32:52.657Z
@a3nm. p,k are part of the input I don't know if the problem is NP hard.
Hao S
CC BY-SA 4.0
2024-01-19T08:26:45.200Z
Thanks. Are the weights on vertices? on edges?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-19T19:38:20.913Z
@a3nm  The weights are on the edges.
Hao S
CC BY-SA 4.0
2024-01-24T20:34:23.430Z
With 2 answers below claiming that the problem is NP-hard and inapproximable (if P != NP) already in the unweighted case, I think there is a remaining interesting question: what happens if $p$ is constant? or if $k$ is constant? The hardness proofs no longer work, but I also don't have a PTIME algorithm.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-24T20:48:54.103Z
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. https://www.sciencedirect.com/science/article/pii/0166218X85900083
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-01-24T21:50:52.077Z
@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).
Neal Young
<graph-theory><graph-algorithms><co.combinatorics><optimization><clustering>
Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes
Hao S
# Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

(Asked by: username_0 on 2024-01-17)

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)

**Tags:** graph-theory, graph-algorithms, co.combinatorics, optimization, clustering

> **Comments:**
> **username_1**: 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?  
> **username_0**: @a3nm. p,k are part of the input I don't know if the problem is NP hard.  
> **username_1**: Thanks. Are the weights on vertices? on edges?  
> **username_0**: @a3nm  The weights are on the edges.  
> **username_1**: With 2 answers below claiming that the problem is NP-hard and inapproximable (if P != NP) already in the unweighted case, I think there is a remaining interesting question: what happens if $p$ is constant? or if $k$ is constant? The hardness proofs no longer work, but I also don't have a PTIME algorithm.  
> **username_1**: 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. https://www.sciencedirect.com/science/article/pii/0166218X85900083  
> **username_2**: @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).  

---

## 2 answers

### Answer by username_2 on 2024-01-24. Score: 2 | Accepted answer

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.


---

### Answer by username_1 on 2024-01-24. Score: 1

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](https://arxiv.org/abs/cs/0210020) to show inapproximability)

> **Comments:**
> **username_1**: 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. ;)  

---

