0
$\begingroup$

I have a special graph in which I have two types of edges only, say one with type 0 and one with type 1. Now I have to find a longest path in the graph such that it starts with a vertex then follows as many type 0 edges as it can and then again start with a vertex and follows as many type 1 edges it can. The length of the longest path will be number of distinct vertices in both the paths. (If some vertex coincide count it once.)

Note : The graph is undirected, heavily contains cycles and has upto 10^6 vertices. So I would need a O(n) algorithm.

P.S : Sorry forgot to give the more important information, for every vertex there are 0 or 2 edges of each type always.

$\endgroup$
  • 1
    $\begingroup$ Finding longest paths is famously NP-hard, so no, there is no known polynomial, let alone linear time algorithm. I don't see how having two types of edges helps any. (The size of your single graph of interest is irrelevant for that. However, it's not too large; maybe simple algorithms are fast enough?) By the way, do you want your graphs to be simple? $\endgroup$ – Raphael Feb 9 '16 at 21:03
1
$\begingroup$

As Raphael pointed out, this problem is also NP-complete. There is an easy reduction from longest path problem to this problem. Just take the graph of longest path problem and label all of the edges type-0. There won't be any type-1 edge. This labeled graph will have a longest path of length $k$ iff original graph has a longest path of length $k$.

This proves the NP-hardness of the problem.

It is easy to see that the problem is in NP, the NDTM machine for the problem will be similar to the longest path problem. Both this add to make the problem NP-complete.

But if you are happy with any kind of approximation, then you can refer Approximation to longest path and modify the algorithm to suit your purpose. However be prepared that the modification may not be trivial.

$\endgroup$
  • $\begingroup$ I have modified the question, see P.S below. $\endgroup$ – Saurabh Jain Feb 11 '16 at 14:05
  • $\begingroup$ Even longest path problem for graphs with nodes of only even degree is NP-complete. Just replace two 2-length path for every edge. $\endgroup$ – Shreesh Feb 11 '16 at 14:08
  • $\begingroup$ And do you mean exactly 0 or 2 edges or atleast 0 or 2 edges? $\endgroup$ – Shreesh Feb 11 '16 at 14:12
  • $\begingroup$ I mean exactly 0 or 2 edges. $\endgroup$ – Saurabh Jain Feb 11 '16 at 14:30
  • $\begingroup$ I have also slightly modified the problem statement. $\endgroup$ – Saurabh Jain Feb 11 '16 at 14:33

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.