Is there any research on the question of finding a spanning subgraph in the form of a collection of independent paths with a maximum number of edges? If the paths are simply edges we have the maximum matching problem which has a polynomial algorithm and up to n/2 edges. But there may be polynomial algorithms that find disjoint paths with more than n/2 edges.

  • 1
    $\begingroup$ This is not easier than existence of a Hamiltonian path (which is NP-hard), since the maximum number of edges is $n - 1$ iff there is a HP. $\endgroup$ – Mikhail Tikhomirov Oct 25 '18 at 6:46
  • $\begingroup$ Yes that's right - whats interesting is how this problem can be approximated in poly time. For example for a Ham graph can you find a set of paths with 3n/4 edges or 7n/8 edges etc. Alternatively can it be shown that you cannot approx. too closely unless P=NP (ie inapproximation results). $\endgroup$ – Richard Taylor Oct 25 '18 at 22:19
  • $\begingroup$ Okay, I see. I would kindly suggest elaborating your question to display what sort of answers you wish to receive (for instance, there is no mention of approximation as of now, are you interested in some other kinds of results as well?). $\endgroup$ – Mikhail Tikhomirov Oct 25 '18 at 23:32
  • $\begingroup$ Have you considered the approximation ratio you get by just computing a maximum matching? If you have a set of vertex disjoint paths containing $k$ edges, these paths contain a matching of size at least $k/2$. So a maximum matching is already within factor $1/2$ from optimal. My guess is that you get a better ratio by starting from a maximum matching and adding edges as much as possible. $\endgroup$ – Manuel Lafond Oct 26 '18 at 0:52
  • $\begingroup$ Thanks Manuel - in fact I have done some work along these lines and starting with a max matching I can get to within 2/3 of the best answer for a general graph and 3/4 for a cubic graph. I posted the problem because I felt surely this is an already studied problem - but I am not keying in to the right language to find it. $\endgroup$ – Richard Taylor Oct 26 '18 at 4:05

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.