-1
$\begingroup$

Suppose $G= (V,E)$ is a directed graph with weights on the edges. I would like to check if $G$ has the following property: if $C \subset E$ is the set of edges in a cycle of length at least $3$, then the weight of at least one of the edges in $C$ is zero. Can this be done in polynomial time?

$\endgroup$
1
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. How far have you gotten? What approaches have you considered? Do you know how to compute the set $C$ in polynomial time? $\endgroup$
    – D.W.
    May 28, 2015 at 6:29

1 Answer 1

1
$\begingroup$

Remove all edges with weight 0 and check that you then have only cycles of length 2 at most that are left.

$\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.