# Partitioning a graph into connected pairs and triplets

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?

• 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". Commented May 28, 2023 at 14:01
• Thank you for your comments! I updated the question. Commented May 29, 2023 at 6:42

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$$.
• 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?! Commented Oct 29, 2023 at 3:25
• @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. Commented Oct 29, 2023 at 5:59