# Algorithm for finding a path factor in a graph

A 1-factor is a perfect matching. A path factor of a graph $$G$$ is a spanning subgraph, each of whose components is a path with at least two vertices (see the following figure).

Since every path with at least four vertices has a $$\{P_2,P_3\}$$-factor, a graph has a path factor if and only if $$G$$ has a $$\{P_2,P_3\}$$-factor.

Deciding whether a graph admits a perfect matching can be done in polynomial time, using any algorithm for finding a maximum cardinality matching (Maximum_cardinality_matching).

My question is, is there a polynomial-time algorithm to determine whether a graph has a path factor? Of course, brute force methods still exist, due to the following characterization of Akiyama, Avis, Era. (On a $$\{1,2\}$$-factor of a graph, TRU Math. 1982)

Theorem A A simple graph $$G$$ has a path factor if and only if

$$i(G-S)\le 2|S| ~~~~~~\text{for all}~~ S \subset V(G),$$ where $$i(G-S)$$ denotes the number of isolated vertices of $$G-S$$.

• Splitting each vertex into two might help! Commented May 15 at 9:35
• Is the problem same as this question Partitioning a graph into connected pairs and triplets? Commented May 15 at 21:27
• @pcpthm Thanks. I juts read it, and the answer seems to say that it may be NP-hard. But it has no any resources. Commented May 16 at 6:30
• That answer links to a paper by Chen et al. I suggest reading the paper and reporting back on whether it is relevant and whether it answers your question.
– D.W.
Commented May 16 at 6:37

There is a paper by Babenko and Gusakov ("New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs"). It discusses the star packing problem. Given an integer $$T > 1$$, a star is a subgraph $$K_{1, t}$$ for some $$1 \leq t \leq T$$. They suggest a polynomial time algorithm for packing vertex-disjoint $$T$$-stars into an undirected graph maximizing the number of taken vertices. For $$T = 2$$ the problem is equivalent to packing connected edges and triplets.

Here is the core idea of the algorithm. For each undirected edge $$(u, v)$$ we introduce two arcs $$(u, v)$$ and $$(v, u)$$. Let the original graph be $$G$$ and the directed graph be $$G'$$.

Let us find a subgraph in $$G'$$ such that for each vertex $$v$$, $$outdeg(v) \leq 1$$ and $$indeg(v) \leq T$$ and maximizing the number of edges. It can be done with the maximum flow algorithm over the following network:

• split each vertex $$v$$ into $$v_{in}$$ and $$v_{out}$$
• for each arc $$(u, v)$$ add an arc $$(u_{out}, v_{in})$$ with unit capacity to the network
• for each vertex $$v$$, add arcs $$(Source, v_{out})$$ with unit capacity and $$(v_{in}, Sink)$$ with capacity $$T$$.

Claim: given such subgraph of $$G'$$ with $$k$$ edges, one can build a star packing in $$G$$ with $$k$$ vertices, and vice versa.

Proof ($$\leftarrow$$): for each star with middle vertex $$v$$ and leaves $$u_1, \dots, u_k$$ pick arcs $$(v, u_1), (u_1, v), (u_2, v), \dots, (u_k, v)$$.

Proof sketch ($$\rightarrow$$): each (weakly) connected component of the subgraph in $$G'$$ is a functional graph, i.e. a cycle where a rooted tree can be connected to each of its vertices. Traverse vertices of those trees in ordered by depth, decreasing. Whenever a vertex $$v$$ is traversed, take its parent $$p(v)$$ and all its siblings, form a star with $$p(v)$$ in the middle and remove all taken vertices from the tree. Some casework is necessary when the cycle is reached, it is left as an exercise to the reader.