10805 - Cockroach Escape Networks

[Abednego]

If you are using the algorithm by Yuqiang Guan and Kenneth Williams, you will get a wrong answer. The same goes for the official solution to a similar problem from a Romanian contest.

I believe that the Guan-Williams algorithm for finding the minimum-diameter spanning tree has a mistake. Here is a test case that breaks it.

Code: Select all

11 vertices, 10 edges:
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 9
9 10

The correct answer is 8, not 7.

[misof]

Most of this post will probably be useful only for abednego, but then, who knows

The Guan-Williams algorithm is (probably ) correct. The bug I made during the contest was in one invalid oversimplification. Guan-Williams say that we need to try splitting some of the edges and checking for a better result. My mistake was in assuming that nothing can go wrong if I try all the edges. As the posted example shows, it can go wrong.

Kudoz to abednego for realizing this.

I'll try implementing the correct version when I have a bit of free time on my hands. We'll see whether it works

[Abednego]

If you read the algorithm description carefully, it will try BFS(10), find that it gives a minimum diameter BFS tree, and then try to split edge 9-10, which will cause it to return 7. I e-mailed the authors, but got no reply yet. It's also unfortunate that they give no formal proof of correctness - they simply state some claims and pretend they are obvious.

The algorithm we are talking about is the one from this page:
http://www.cs.utexas.edu/users/yguan/pa ... node2.html

Thanks to everyone who sent clarifications during the contest.

[domino]

If you read the algorithm description carefully, it will try BFS(10), find that it gives a minimum diameter BFS tree, and then try to split edge 9-10, which will cause it to return 7. I e-mailed the authors, but got no reply yet. It's also unfortunate that they give no formal proof of correctness - they simply state some claims and pretend they are obvious.

The algorithm we are talking about is the one from this page:
http://www.cs.utexas.edu/users/yguan/pa ... node2.html

Thanks to everyone who sent clarifications during the contest.

I've implemented this algorithm and it returns 8 on your test case. I didn't assume at each edge splitting that if one removes the inserted vertex the tree will have d(T)-1 diameter, i simply recalculate the diameter for the tree on each edge splitting. I've tested on a lot of random test cases and made a validator the check if the result outputted is valid (i also output a tree and i check to see if this tree has the diameter i say) and i've also gotten max points in the Romanian contest you were talking about, but still i get WA here at UVA...

[nnahas]

If you read the algorithm description carefully, it will try BFS(10), find that it gives a minimum diameter BFS tree, and then try to split edge 9-10, which will cause it to return 7. I e-mailed the authors, but got no reply yet. It's also unfortunate that they give no formal proof of correctness - they simply state some claims and pretend they are obvious.

The algorithm we are talking about is the one from this page:
http://www.cs.utexas.edu/users/yguan/pa ... node2.html

Thanks to everyone who sent clarifications during the contest.

First, a disclaimer: I didn't even attempt to implement the algorithm, but my point of view is that the algo is correct , like domino implemented it,
computing the diameter of the tree for each BFS Tree . Here is an attempted proof.

Case 1: The minimum diameter spanning tree T has an odd diameter d(meaning the longest path has an odd number of vertices.)
First we notice that the diameter of each BFS tree is an upper bound on the diameter of T. Let P be a path of length d in T. Let v be the midpoint of P. Let T' be the BFS tree rooted at v. We have to prove that T' has diameter d. let dist(i,v) be the function that assigns to each node i its distance to v in the original graph and let dist'(i,v) the function that assigns to each node its distance to v in the tree T. Since T is a subset of the graph dist(i,v) < dist'(i,v) . Suppose now there is a node q in T such that dist'(q) > d/2 . this node q cannot be at the same time in the same subtree of T than the two extremities of P, since the two extremities are each in a different subtree. So a path from q to one of the extremities of the P must be longer than P which contradicts the fact that P is a longest path in T. Therefore for all nodes q we have dist'(q) <= d/2 . therefore we have for all nodes q dist(q) <= d/2 . Therefore we know that in T' all nodes will be at a distance of d/2 at most from the root, so the T' must have a diameter of d at most. So we are sure that at least one of the BFS trees has a diameter equal to the minimum diameter.

Case 2: The minimum diameter spanning tree T has an even diameter d(meaning the longest path has an even number of vertices.)

Proof coming soon

[nnahas]

[
Case 2: The minimum diameter spanning tree T has an even diameter d(meaning the longest path has an even number of vertices.)

Mmm, well, this case would be equivalent to the previous one *IF* we could prove that splitting the edge in T that links v (which is defined to be one of the two midpoints of P) to the subtree containing its deepest child would make the diameter equal to d+1. But I am not able to prove it, because nothing tells us that the path P is the shortest path between its extremities in the original graph.

But it is not too hard to slightly change the algorithm so that a correctness proof becomes feasible. Instead of splitting edges, let us adopt the following algorithm (which is only O(N^3) ):

1- Get a BFS Tree for each vertex.
For each such BFS tree do the following
a- Let MaxDist be the maximum distance to the root for any vertex in the BFS Tree
b-Get the list of all nodes that are at a distance MaxDist from the root.
c-Try to find a BFS Tree such that all these nodes are descendants of the same child of v. if such a BFS tree exists , then there is a tree of diameter 2*MaxDist, otherwise all we can say is that there is a tree of diameter 2*MaxDist +1. That value will be an upper bound on the diameter.
the least upper bound will be the diameter of the optimal Tree T..

There are 2 issues to address here : the first is the feasibility of step c, and the second is the correctness of this algorithm.

We can implement step c by precomputing a distance table using Floyd-Warshall. Then for each vertex adjacent to the root we check if all the vertices that are at distance MaxDist from the root are at a distance of MaxDist -1 from the child in question . so step c is definitely feasible.

In fact this algorithm is incredibly easy to implement . 10-15 lines should do it. Will anyone volunteer and do it and tell us if it works ? I would have done it myself but the I/O code is tedious to write ,and I don't have any of it ready as I didn't take part in the contest.

OK, so now the correctness proof :
Once again, let d,T,P ,dist'(i,v) be as defined in my first post on this thread. v is one of the 2 midpoints of P. Then we are sure that only one of the subtrees of T rooted at one of the children of v are has nodes at a distance of d/2, otherwise there would be path of length greater than d joining the deepest vertices of two subtrees (It would be of length d+1) actually. We still have to prove that the existence of T implies the existence of a BFS tree rooted at v having the same property as T (namely that all its deepest nodes are the descendants of the same child of v.)
I'll leave that to a later message. Stay Tuned

[nnahas]

We still have to prove that the existence of T implies the existence of a BFS tree rooted at v having the same property as T (namely that all its deepest nodes are the descendants of the same child of v.)
I'll leave that to a later message. Stay Tuned

First , my remark that the code would be very easy to implement referred to the computation of the minimum diameter, not the actual tree.
Getting the actual tree isn't too hard but it isn't "incredibly easy" to implement.

Second, here is the remaining part of the proof. By starting a BFS search at one of the children c of v that are at a distance of MaxDist -1 of the vertices that are at a distance MaxDist of v, we assign distance labels to the all the vertices, if we add 1 to each distance label, we would obtain the length of the shortest path from v going through c to the labeled vertex. Running Bellman-Ford rooted at v afterwards will not modify the labels of those vertices for which a shortest path that goes through c exist. so the part of the BFS tree that contains the node at a distance of MaxDist will remain unchanged. Finally we note that the existence of at least one node at a distance of MaxDist from v in T implies the existence of a node at a diatnce of MaxDist from v in the original graph, otherwise a BFS tree rooted at v would have a smaller diameter than T.
running time :
O(N^3) Floyd Warshall
O(N^2) To get MaxDist for each node.
O(N^3) to get a c for each v or to verify none exist.
O(N^3) to get all the BFS subtrees O(N^2) per subtree

Total running time O(N^3)

OK, I realize that there may be lots of things that are unclear , and maybe wrong, in what I said. Questions and requests for clarifications are welcome.

[nnahas]

If you are using the algorithm by Yuqiang Guan and Kenneth Williams, you will get a wrong answer. The same goes for the official solution to a similar problem from a Romanian contest.

I believe that the Guan-Williams algorithm for finding the minimum-diameter spanning tree has a mistake. Here is a test case that breaks it.

Code: Select all

11 vertices, 10 edges:
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4 9
9 10

The correct answer is 8, not 7.

I think you misinterpret what the Guan Williams algorithm says. When they say odd diameter, they mean an odd number of vertices on the longest path, not the sum of edge costs along the path. so here the diameter they find is 9, and there's no need for edge splitting.

Nevertheless, they did forget to specify that the BFS tree must at least have 2 branches, and the depth of the two deepest differing by at most 1.
The reason behind this constraint is to make the root of the BFS tree a valid candidate for the job of longest path midpoint.

[Abednego]

I'm worried that after a couple of days, there is still no correct solution to this problem. domino, could you email me your code (abednego at gmail), and I will check by hand all the cases where our answers differ?

[Cosmin.ro]

I'm the problemsetter of a similar problem in the Romanian contest abednego is talking about. The official solution I used in that contest outputs 8 not 7 on the example given above, I've implemented the algorithm sugested by the link mentioned before. Also I wanted to add that in the Romanian contest it was intended for a solution to get maximum points only if it implemented a O(n^3) or lower algo, in fact Domino's solution was fine tuned O(m*m) and it got full marks. My O(n^3) solution is similar to nnhas ideeas, and if instead of computing the distance matrix with Roy Floyd we use n breadth first searches then we get a O(n*m) algorithm.
nnhas if you need to see a sourcecode I can send it to you but my implementation is in pascal, also my problem asked for the tree not only the diameter so I find the tree as well.

[nnahas]

I'm the problemsetter of a similar problem in the Romanian contest abednego is talking about. The official solution I used in that contest outputs 8 not 7 on the example given above, I've implemented the algorithm sugested by the link mentioned before. Also I wanted to add that in the Romanian contest it was intended for a solution to get maximum points only if it implemented a O(n^3) or lower algo, in fact Domino's solution was fine tuned O(m*m) and it got full marks. My O(n^3) solution is similar to nnhas ideeas, and if instead of computing the distance matrix with Roy Floyd we use n breadth first searches then we get a O(n*m) algorithm.
nnhas if you need to see a sourcecode I can send it to you but my implementation is in pascal, also my problem asked for the tree not only the diameter so I find the tree as well.

Well now I do have my own implementation but I'm getting WA. I'll try to fix it.
If I can't I'll write a brute force routine and test it on random graphs.
If everything turns out to be all right, I'll send my program to Abednego so that he checks his program.

[Abednego]

domino, your algorithm returns 4 on the following test case. The correct answer is 3.

Code: Select all

25 182
0 1
0 3
0 4
0 6
0 7
0 9
0 10
0 12
0 16
0 19
0 21
0 22
0 23
0 24
1 2
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 17
1 19
1 20
2 3
2 5
2 6
2 8
2 10
2 11
2 14
2 16
2 17
2 20
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 19
3 20
3 21
3 22
4 5
4 6
4 7
4 8
4 9
4 10
4 11
4 15
4 19
4 20
4 22
4 23
5 7
5 8
5 11
5 12
5 13
5 15
5 16
5 17
5 19
5 20
5 23
5 24
6 8
6 10
6 12
6 13
6 14
6 15
6 16
6 17
6 18
6 20
6 24
7 8
7 9
7 10
7 11
7 12
7 13
7 14
7 15
7 17
7 21
7 22
7 23
7 24
8 10
8 11
8 14
8 15
8 17
8 18
8 19
8 20
8 21
8 23
8 24
9 11
9 13
9 15
9 16
9 19
9 21
9 22
9 23
9 24
10 11
10 13
10 14
10 15
10 16
10 17
10 18
10 19
10 22
10 24
11 13
11 16
11 17
11 18
11 19
11 21
11 22
11 23
11 24
12 13
12 14
12 17
12 21
12 22
13 14
13 16
13 17
13 20
13 23
13 24
14 15
14 16
14 18
14 20
14 22
14 23
15 17
15 20
15 24
16 19
16 21
16 22
16 23
17 18
17 19
17 20
17 21
17 23
18 22
18 23
18 24
19 20
19 21
19 24
20 22
20 23
21 22
21 23
21 24
22 24
23 24

The answer is 3 because when you do BFS from vertex 11, 11 will have children:
1,2,3,4,5,7,8,9,10,13,16,17,18,19,21,22,23,24. and 1 will have children 0,6,12,14,15,20.

[Cosmin.ro]

My result wich should be the same as domino's since we implemented the same algorithm is 3.

[nnahas]

My result wich should be the same as domino's since we implemented the same algorithm is 3.

Mine too returns 3 on this example. But maybe I have done a subtle error ?
I check for the case with a single nest. I append a newline after each test case, including the last. I start with Case#1 not Case #0.
I capitalized the C. Are there other details of that kind that I should check ?

[Abednego]

Thanks a lot to domino and Cosmin.ro. I found a bug in my solution, once again. The output file should be changed soon.