1
$\begingroup$

Given a simple undirected connected graph. What is the minimum number of edge-disjoint paths needed to cover all edges of the graph? I have only found information about the vertex-covering one.

My friend suggests that such value equals u/2, with u being number of vertices with odd degree, or 1 if there is no such vertices.

Can anyone confirm if his assumption is correct or not?

$\endgroup$
3
$\begingroup$

Assuming that the "paths" we're talking about are actually trails, that is, walks that may repeat vertices but may not repeat edges (which seems to be the most natural context for requiring them to be edge-disjoint), that sounds right to me.

Clearly at least that many paths will be needed, and it's not too difficult to see that you can construct a covering at set of exactly that many paths greedily:

  1. Start at an odd-degree vertex, and walk along random unused edges until you there's nowhere you can go. At that time you must have reached another odd degree vertex.

  2. Continue doing this as long as there are odd-degree vertices left.

  3. If there are still unused edges in the graph, locate a vertex that is touched by both used and unused edges. Break one of the paths you have already identified through that vertex, and start walking randomly along unused edges from there. Since you've used up all of the odd vertices, the only place you can end is at the vertex where you started, so you can then proceed along the rest of the original path, so the number of paths doesn't increase.

  4. Repeat until all edges have been covered.

$\endgroup$
  • $\begingroup$ So can it be extended to DAGs? $\endgroup$ – FallingStar Nov 24 '16 at 15:59
  • $\begingroup$ @FallingStar: Yes, in the appropriate generalization. For directed graphs, you'd need as many paths to start at each node as its out-degree exceeds its in-degree, but these are all you need (unless that sums up to $0$, in which case you need $1$). $\endgroup$ – Henning Makholm Nov 24 '16 at 16:09
  • 1
    $\begingroup$ It would be well to include a definition of "path" somewhere in the question or the answer, especially since the term is not being used in what I would consider the standard sense. $\endgroup$ – bof Sep 5 '17 at 1:19
  • $\begingroup$ Will this give the minimum number of paths? Is finding the minimum number of paths NP-complete? $\endgroup$ – Eyal Dec 11 '17 at 16:47
  • $\begingroup$ @Eyal: Yes to the first -- it is easy to see the you can't get away with fewer paths than this procedure produces, because a path needs to begin or end at each odd-degree node. (This assumes that the "paths" we're talking about are actually trails, that is, walks that may repeat vertices but may not repeat edges). $\endgroup$ – Henning Makholm Dec 11 '17 at 18:03
1
$\begingroup$

In a directed graph, we can transform this into a flow problem with each edge having the lower-bound capacity of $1$ and all link to a source and a sink with edges with lower-bound capacity $0$. The least number of paths will be the minimum flow value. Is this idea correct and if so can it be generalized to 'undirected graph'?

$\endgroup$
  • $\begingroup$ I believe that for directed graph it's correct but I'm not so sure about lower-bound capacity flow for undirected graph. $\endgroup$ – FallingStar Dec 1 '16 at 15:36

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.