Two related things I have heard/know of are,

(1) That there exists a polynomial algorithm to find a cover of the vertices by $k$ vertex disjoint cycles. (Can someone give a reference for this?)

(2) That its NP-complete to decide if $k$ vertex disjoint paths can cover all the vertices of a graph.

  • Are there edge analogues of these results?

  • Does using the dual graph translate these results into their edge versions?

  • If the line graph is a edge-to-vertex-dual then is there a vertex-to-edge-dual? (which will may be convert the question of finding a vertex cover by k vertex disjoint paths into a question of finding an edge cover by $k$ edge disjoint paths?)

  • 2
    $\begingroup$ Although they are closely related, that is quite a lot of questions for one question. Stack Exchange usually works best with only one question or, at least, questions so closely related that it's likely that somebody will know the answers to all of them. Maybe this one's best left as it is, now, but something to bear in mind for next time. $\endgroup$ – David Richerby Sep 13 '14 at 7:20

You can cover the edges of a graph by cycles iff the graph is Eulerian (or has multiple Eulerian components). Notice that two cycles that share a vertex can always be combined into one cycle.

  • $\begingroup$ Juodele I am talking of covering the edges of the graph by k edge disjoint "paths". Is anything known about this? $\endgroup$ – guest Sep 13 '14 at 13:34
  • $\begingroup$ Juodele I think it is in P to find an edge cover with k edge disjoint paths. Take your graph and suspend it from a vertex - then add self-loops to all the odd degree vertices - now find an Eulerian tour on it - then remove the new vertex and its edges - then what you are left with is an edge cover of the original graph - if this cover has >k pieces then combine them to get to k and if they have less than k pieces then split them to get to k - $\endgroup$ – guest Sep 13 '14 at 17:17
  • $\begingroup$ since the graph is connected every two paths of an edhe covering path set must share a common vertex and hence any two paths can be combined whenever necessary - you only combine a path p1 with path p2 if in the lifted Eulerian tour the p2 came just after p1 $\endgroup$ – guest Sep 13 '14 at 17:23
  • $\begingroup$ @guest, title says cycles. Is that an error? $\endgroup$ – Karolis Juodelė Sep 13 '14 at 21:05
  • $\begingroup$ Juodele Sure! Corrected the typo! $\endgroup$ – guest Sep 14 '14 at 15:00

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.