5
$\begingroup$

We need to partition an undirected graph into connected subgraphs of size between $2$ and $k$, where $k$ is an integer.

When $k=2$, the problem is equivalent to the perfect matching problem which is known to be solvable in polynomial time.

When $k=3$, the problem is similar to the partition into triangles problem, which is proved to be NP-complete by reduction from 3-dimensional perfect matching problem. But there are two differences: first, we allow subgraphs of size 2; And second, we allow subgraphs of size 3 that contain only two edges (i.e. paths).

Is there a polynomial-time algorithm for this problem, assuming $k=3$? Assuming $k$ is fixed? Assuming $k$ is part of the input?

$\endgroup$
2
  • 1
    $\begingroup$ The conventional meaning of "a connected component" is "a connected subgraph that is not part of any larger connected subgraph". Do you mean to "find a partition of the vertices of a graph so that each subgraph is connected with at most $k$ vertices"? Or you can redefine "connected component". $\endgroup$
    – John L.
    Commented May 28, 2023 at 14:01
  • $\begingroup$ Thank you for your comments! I updated the question. $\endgroup$
    – Chaya
    Commented May 29, 2023 at 6:42

1 Answer 1

4
+100
$\begingroup$

The problem can be solved in the polynomial time for $k = 3$.

There is this paper by Chen et al.. The authors design an approximation algorithm for the minimum $3$-path partition problem. The minimum $3$-path partition problem is similar to your problem. It aims to partition the graph into minimum number of vertex disjoint paths each of size at most $3$. The only difference between this problem and your problem is that it allows a partition of size $1$, i.e., a singleton vertex.

In Section $2$, of the paper, authors design a polynomial time algorithm for computing $3$-path partition with the least number of $1$-paths ($1$-path means a singleton vertex). They further use this algorithm to design an approximation algorithm for the minimum $3$-path partition problem. However, this polynomial time algorithm gives a straightaway solution to your problem. If the algorithm returns a solution with non-zero number of $1$-paths, then the graph can not be partitioned into connected subgraphs of size between $2$ and $3$. And, if the algorithm returns a solution with no $1$-paths, then the graph can be partitioned into connected subgraphs of size between $2$ and $3$.

$\endgroup$
4
  • $\begingroup$ This is very surprising: if we allow paths of lengths $1,2,3$, or paths of length 3 only, then the problem is NP-hard; but if we allow paths of length $2,3$, the problem is in P?! $\endgroup$ Commented Oct 29, 2023 at 3:25
  • $\begingroup$ @ErelSegal-Halevi Please note that in your problem, you asked for existence of a partitioning. However, the minimum path partition problem asks for a feasible partitioning with the minimum number of partitions. Indeed, in polynomial time you can find a feasible partitioning of paths of lengths $1$, $2$, and $3$; simply take all singleton partitions. $\endgroup$ Commented Oct 29, 2023 at 5:59
  • $\begingroup$ Ah, I see. So if we want to find a partition with a smallest number of paths of lengths 2,3, this will probably be NP-hard. $\endgroup$ Commented Oct 29, 2023 at 16:06
  • $\begingroup$ @ErelSegal-Halevi yes. Right! $\endgroup$ Commented Oct 29, 2023 at 16:36

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.