5
$\begingroup$

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).

enter image description here

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$.

$\endgroup$
4
  • 1
    $\begingroup$ Splitting each vertex into two might help! $\endgroup$
    – codeR
    Commented May 15 at 9:35
  • $\begingroup$ Is the problem same as this question Partitioning a graph into connected pairs and triplets? $\endgroup$
    – pcpthm
    Commented May 15 at 21:27
  • $\begingroup$ @pcpthm Thanks. I juts read it, and the answer seems to say that it may be NP-hard. But it has no any resources. $\endgroup$
    – licheng
    Commented May 16 at 6:30
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented May 16 at 6:37

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

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.