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?
$\begingroup$
$\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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Remove all edges with weight 0 and check that you then have only cycles of length 2 at most that are left.