0
$\begingroup$

For any directed/undirected labelled graph G := (V,E,L), where L is the finite set of labels, and every edge has a label. For simplicity, let us assume that L = {a,b}. Is there a P-time algorithm to determine whether all possible cycles passing through a vertex "v" has at least one edge (every cycle) with label "a"? We can assume that G is simple with self-loops.

The naive approach would be to enumerate all possible cycles passing through "v" and then check every edge label. I was thinking of a more efficient approach, to eliminate traversing some repeated paths based on whether "a" was encountered/not, and reduce the complexity to that of DFS - I cannot decisively conclude for now that this will be P-time.

$\endgroup$

1 Answer 1

0
$\begingroup$

The question is equivalent to asking whether there exists a cycle that goes through $v$ and uses only b-edges. This can be tested by deleting all a-edges, then testing whether the resulting graph has a cycle that goes through $v$ using any standard algorithm. This gives an algorithm that runs in polynomial time -- in fact, in linear time.

$\endgroup$

Your Answer

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

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