A graph G has n vertices and m edges The Minimum Cycler of G is a set S of edges of minimum total weight such that every cycle in G contains at least one edge in S. Devise an algorithm that finds the Minimum Cycler in O(m log n) time

My Approach-
Consider a cycler S. We can reduce our focus only to the cycler with minimal
set of edges. ie. if we remove any edge from the cycler than it ceases to
remain a cycler. Because all other cyclers are not useful or won't anyways
count as one with minimum edge sum.
Now given a reduced cycler (or a minimal one) my target is to prove that
G\S is a spanning tree.
To show this we will have to prove that :

  1. G\S is acyclic
  2. G\S is connected

(1) is trivial as if G\S has a cycle than S is not a cycler.

(2) Suppose G\S is disconnected. Let E be the minimal set of edges that
we can add to G\S to make it connected. So we have G\S+E.This cannot have
a cycle because otherwise E won't be the minimal set of edges which will make
it connected. Now consider S-E. Will this be a cycler is one question and
whether S will have some edges in common with E is another. S-E will be
a cycler because if there is any cycle in G than that had an edge in S
I am stuck here unable to extend this argument to reach its final stage

  • $\begingroup$ Hint: if $G$ is connected and all weights are positive, then you can show that $E \setminus S$ is a spanning tree. $\endgroup$ – Dmitry Apr 16 at 14:52
  • $\begingroup$ I have tried proving it. Updated in the question but stuck with the argument at one stage. $\endgroup$ – rohit sharma Apr 18 at 18:40
  • $\begingroup$ Now consider S-E. Will this be a cycler - it will, since $G \setminus S + E$ doesn't have cycles (otherwise, $E$ is not a minimal set of edges to make the graph connected). whether S will have some edges in common with E is another: $E \subseteq S$ since $E$ doesn't belong to $G \setminus S$, i.e. $E \subseteq G \setminus (G \setminus S) = S$. $\endgroup$ – Dmitry Apr 19 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.