0
$\begingroup$

Given an undirected graph $G=(V,E)$. We want, if possible, to partition $G$ into paths of length 2 such that each pair of paths is edge-disjoint. I seek an algorithm with linear time $O(V+E)$ and a proof that shows us why the algorithm is correct.

My idea is that we can't partition any graph this way. But when we can, we can use DFS to partition our graph. But I can't formulate my idea.

$\endgroup$

1 Answer 1

2
$\begingroup$

We only need to consider the case in which the graph is connected and number of edges is even. We hence assume the above conditions once for all.

As a first observation, notice that if the graph is a star then it can easily be partitioned.

You can then show by induction that other graphs can also be partitioned. The induction is on the number $m$ of edges. If the graph has $0$ edges then the claim is trivial.

Consider an even value of $m>0$. If $G$ is a star we are done. Otherwise, since graph has at least $2$ edges, and we can compute an arbitrary rooted spanning tree $T$. Let $u$ be the deepest leaf of $T$. If there are multiple choices for $u$ prefer a vertex that has at least one incident non-tree edge. Let $v$ be $u$'s parent, and let $w$ be $v$'s parent (if any).

  • If $u$ has at least $2$ incident non-tree edges, then select and remove them.

  • Otherwise, if $u$ has exactly $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.

  • Otherwise, if $v$ has at least $1$ incident non-tree edge $e$, select and remove the path containing $e$ and $(u,v)$.

  • In the only remaining case neither $u$ nor $v$ have incident non-tree edges. Moreover $w$ exists, since otherwise $v$ would be the root $T$, $T$ would have height $1$, and no child of $v$ would have any incident non-tree edge, implying that $T$ is a star. Select remove the path containing $(u,v)$ and $(v,w)$.

Ignore any vertex whose degree has been reduced to $0$. The remaining graph has $m-2 \ge 0$ edges, and the claim follows by invoking the induction hypothesis.

The above proof immediately leads to a liner-time algorithm once you observe that the spanning tree of the graph needs to be computed only once.

$\endgroup$
4
  • $\begingroup$ Thank you, why we need the graph should be connected? $\endgroup$
    – Ahmad
    Nov 6, 2021 at 18:00
  • $\begingroup$ We don't need the graph to be connected but we can assume without loss of generality that it is (otherwise we can handle each connected component separately) $\endgroup$
    – Steven
    Nov 6, 2021 at 18:12
  • $\begingroup$ Can you explain why in case 1, if $u$ have at least two non-tree edges, we remove them? $\endgroup$
    – Ahmad
    Nov 6, 2021 at 22:15
  • $\begingroup$ Also, why in each step $m$ reduced by exactly 2 unit? In case 1 maybe we remove more than 2 edges... $\endgroup$
    – Ahmad
    Nov 6, 2021 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.