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.

Improve this question
$\endgroup$
1
  • 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, 2016 at 21:03

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I have modified the question, see P.S below. $\endgroup$
    – Saurabh Jain
    Feb 11, 2016 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$
    – Sarvottamananda
    Feb 11, 2016 at 14:08
  • $\begingroup$ And do you mean exactly 0 or 2 edges or atleast 0 or 2 edges? $\endgroup$
    – Sarvottamananda
    Feb 11, 2016 at 14:12
  • $\begingroup$ I mean exactly 0 or 2 edges. $\endgroup$
    – Saurabh Jain
    Feb 11, 2016 at 14:30
  • $\begingroup$ I have also slightly modified the problem statement. $\endgroup$
    – Saurabh Jain
    Feb 11, 2016 at 14:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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