Problemset 7

Adrian_Kosowski 2005-03-08 23:03:51 UTC #1

Problemset 7 is now over. You are invited to post any remarks or questions concerning the problems, as well as short descriptions of your accepted solutions.

Pascal_sof 2005-03-11 11:48:33 UTC #2

Here is what I did for TWORK (I will let Adrian explain his approach for the two challenge problems).

The input is a graph with n mod 4 = 0 and in which each node has degree 2 or 3. The problem amounts to find a maximal vertex cover (also known as vertex packing) using only "carets" or 3-paths (3 nodes and 2 edges), such that at least 3/4 of the nodes are covered.

I start by building a cover tree for the graph, and root it with a node with degree at most 2. This way we have a binary tree, with at most 2 sons for every node. Then, I use a bottom-up traversal, trying to pack as much carets as possible. The non-trivial is when we consider a node with 2 sons. When each of them has been packed, they contain 0, 1 or 2 nodes each. When there is a 0, the considered node does not really have two sons anymore, and we continue packing trivially. If there are 1 and 1, we can place a caret. If there are 1 and 2, we also place a caret, leaving one node uncovered (but since we cover 3 others, we still respect the 3/4 bound). The bad case is when we have 2 and 2 sons. Then, we place a caret BUT leave 2 nodes uncovered, which means one too much.

Now, notice that for all trivial packing (case 0-x and case 1-1), we actually save one node there. Since generally speaking there will be more such cases than the bad cases, we should still respect the 3/4 bound in the end.

There are only few cover trees with n mod 4 = 0 that cannot be covered with carets. The simplest such example is:

which cannot be covered with 3 carets. When such a case happens, we only need to construct another random cover tree of the initial graph and start again. If the problem is solvable (I would be happy to see a proof), we must find a convenient cover tree at some point, and in practice it turned out to be pretty efficient.

Adrian_Kosowski 2005-03-11 16:51:58 UTC #3

A slight modification of your algorithm guarantees "getting it right first time" . The only possible structures in the spanning tree that can spoil the 3/4 bound are 3 vertex paths, whose successive vertices have degrees 3, 2 and 1 (the tree in your figure contains 4 such paths ). In order to get rid of them it suffices to build the tree using the DFS algorithm, and then reattach any DFS leaf at the end of an undesirable path to some other vertex of the tree. This is always possible (since the original graph has vertices of degree 2 or higher) and no new undesirable structures will be created in the process (this is a consequence of the adopted DFS approach). Thanks to the assumption that 4|n we don't need to worry about the single leaf unaccounted for (namely, the DFS root). As a matter of fact, it is also possible to choose the root "the right way" for any graph of order n!=1,2,5, but this requires a little additional effort.

Pascal_sof 2005-03-13 11:37:53 UTC #4

Nice proof, I like it
Btw, I am pretty sure you can improve the bound for larger n. What is the general result ?

Adrian_Kosowski 2005-03-14 02:05:08 UTC #5

The bound is asymptotically tight. To prove this, simply consider the following graph: take a perfectly balanced binary tree; insert 2 vertices into all its edges which are not incident to a leaf; replace all leaves with 5 vertex cycles.

As a matter of fact, the test data was largely composed of such graphs (give or take a little randomness in ordering and a few extra edges) .

Adrian_Kuegel 2005-03-14 04:06:59 UTC #6

First I selected all edges that were the only outgoing edges from some nodes. Then I selected the cheapest edges from nodes with 2 or 3 edges (ignoring the costs that are caused by intersections). After that, I run a modified kruskal algorithm that selects the cheapest edge that connects two parts that are not yet connected. For this I also consider how many intersections with already selected edges exists. Since this greedy doesn't work so well, I divided the intersection costs by 3 to give the other costs more weight.

Adrian_Kuegel 2005-03-14 04:12:59 UTC #7

I used pure greedy for this problem. I build the output string from left to right. I keep a priority queue of k entries which indicates the next available position in each of the k copies of the string. For each position, I select among the unused words the longest word that matches every character after that position. Then I extend the string with the new word inserted at the current position.