minimum edge for deletion

[asif_rahman0]

can someone explain the algorithm of this problem???

Code: Select all

    1
   / \ \
 /    \  \
2     \   \ 
 \-----3-- 4
  \
   \
    \
     5

How can i find the minimum number of edge that i have to delete from the graph that all vertices have even number of edges?

[bugzpodder]

this is from the IOI 2006 practice right? (or close to it anyways, since the problem asks for all vertices to have odd degree but I think the same algorithm works) http://www.ioi2006.org/practice/highways.pdf

Please state your source if its different.

I've come up with this algorithm, i am not sure if its entirely correct.

Observation 1: If we have a graph with all n vertices odd [degree] (hence even number of vertices), then we can remove odd cycles until there is none left so there less than n edges. This is easy to see as since when there is no cycles, then the graph is a forrest. but you've probably figured this out already.

Observation 2: If you remove a walk that has only start and end vertices even, you've reduced the number of even vertices by exactly 2. This is easy to see.

Observation 3: The problem (IOI) have a solution if and only if the number of even vertices is even (since the graph is connected), which is true if and only if the number of vertices is even (since there is an even number of odd vertices by handshaking lemma). This is a little bit harder to convince one of. Essentially the graph is connected we can find a walk between any pair of vertices. the problem is of course when two edges of two walks overlap, then essentially we cancel them out by not removing the edge. Hence this algorithm is linear.

In the problem in this thread, essentially apply observation 2/3 but interchange all the even/odd.

Can anyone comment on the correctness? I'd like to know. It seemed correct to me.

[chrismoh]

I haven't really thought about the original problem, but there could be a simple solution to it.

For the IOI 2006 practice, here's a simple algorithm that solves it:

(1) Do a DFS traversal, generate the DFS tree.
(2) If all nodes in the tree have odd degree, stop
(3) Choose the node with greatest height (i.e. lowest in the tree) that has even degree. Separate it from its parent, thus making it odd degree. Note that this may make its parent become even degree. Note that this node will never be a leaf, since leaves have degree 1.
(4) Go to (2).

If in step (3) you find that you reach the root and the root is even degree, there is no solution. (why?)

The trick about the IOI problem is that you don't have to find the optimal solution, just some solution that has at most c edges.

To find the optimal solution is probably a lot harder. There might be some flow/cost formulations involved, but I'm just speculating...

[asif_rahman0]

thnx a lot to chrismoh and bugzpodder. I got the idea now.
In UVa, there is a problem(10968) for all even vertices.

bye
rabbi

[chrismoh]

10968 is different.

Note that 10968 has at most 2 cities that have odd degree.

So:

If 0 cities have odd degree, we're done.
If 1 city has odd degree, there is no solution.
If 2 cities have odd degree, find the shortest path between the two cities and burn all the roads in this shortest path.

To ensure that every city has a neighboring city after deletion, don't consider cities of degree 2 when doing shortest path.

[asif_rahman0]

Thanks chrismoh.
But i am getting TLE.
Used simple BFS().

Algorightm:
1. find Start odd vertex and destination odd vertex.
2. then run bfs() and not go when found 2 degree vertex and if find des then
break from bfs(). just print the cost[des].

bye
rabbi

[DJWS]

Hiya.
This problem sounds like 'Chinese Postman Problem' with all edge cost equaling 1.

--
DJWS, a newbie in programming

[chrismoh]

asif_rahman0:

I coded a simple BFS with an adjacency matrix (which isn't the most efficient) and got Accepted in about 0.2s. Hopefully you aren't having an infinite loop or something.

DJWS:

I don't think you can transform the problem directly to a chinese postman. Chinese postman is when you want to visit all edges at least once with the minimum cost. The difference is that in Chinese postman you can visit an edge more than twice, while in this problem you can only remove an edge once. So the cost formulation is different (in Chinese postman you can run a min-cost matching on a general graph with vertices the odd degree vertices in the original graph and cost the shortest path between the vertices because you are allowed to count the cost of any edge more than once or twice - here you can only count the cost of an edge once).

[mf]

in Chinese postman you can run a min-cost matching on a general graph with vertices the odd degree vertices in the original graph and cost the shortest path between the vertices because you are allowed to count the cost of any edge more than once or twice - here you can only count the cost of an edge once.

Think a bit deeper. In a minimum cost matching, no two shortest paths can have a common edge. (See figure 6.16 on this page.)
So you won't erase an edge more than once

[chrismoh]

Hmm. That's true.

So you can indeed solve this with a minimum cost matching.

thanks for the tip

[Dimitar]

About the IOI problem..

I can't figure out an algorithm that could handle with this case:

number of vertices - 4
number of edges - 6 - (1,2) (1,3) (1,4) (2,3) (2,4) (3,4)

Code: Select all

         1
        /|\
       / | \
      /  |  \
     /   |   \
    /    |    \
   /     |     \
  3------2------4
   \___________/

Or more generally, what to do when all vertices are odd but the number of edges is greater than then the number of vertices?

[bugzpodder]

Dimitar look at my first post in this topic. (observation 1). Also, my algorithm for the IOI practice can be simplified to just a O(1) check on the number of vertices is even, since the graph is connected and so there must be an odd number of odd vertices.

[bugzpodder]

can anyone tell me if my algorithm above is wrong by showing me a flaw or come up with a counter example? an O(1) algorithm just seemed not right.

[chrismoh]

since the graph is connected and so there must be an odd number of odd vertices

A graph *never* has an odd number of odd vertices, since that would imply that total degree is odd.

I think what you are saying is that since the total degree of a graph is even, hence for every vertex to have odd degree, the number of vertices must be even.

I believe the O(1) algorithm you give is right to determine existence, assuming the graph is connected. It can be proved by induction on the algorithm I gave in my first post.

However, for this problem, proving existence is not enough. You need to actually give a solution for the problem i.e. actually printing the correct edges.

The algorithm I gave in my first post is easily implementable and runs in linear time

[Dimitar]

Now crhismoh, your algorithm is wrong..

It could solve the problem of making all vertices in a graph with an odd degree, but in the IOI problem there's an additional constraint - the number of the edges in the solution should be less or equal to the number of vertices. This is where your algorithm fails.

For example for the graph above, your algorithm would stop at point 2) immediately (all vertices are of odd degree), but this won't be a correct solution, because the number of edges is 6, and the number of vertices is 4.