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
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 :
- G\S is acyclic
- 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