Editorial for IOI '07 P6 - Training


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Detecting an odd cycle in a graph is a well-known problem. A graph does not contain an odd cycle if and only if it is bipartite. On the other hand, the problem of detecting an even cycle in a graph is not widely known.

We are given a graph consisting of N vertices and M edges. Exactly N-1 edges are marked as tree edges and they form a tree. An edge that is not a tree edge will be called a non-tree edge. Every non-tree edge e has a weight w(e) associated with it.

The task asks us to find a minimum-weighted set of non-tree edges whose removal results in a graph that does not contain a cycle of even length. We will call such a cycle an even cycle. Reasoning backwards, starting from a graph containing tree edges only, we have to find a maximum-weighted set of non-tree edges that can be added to the graph without forming any even cycles. In order to describe the model solution, we first need to make a few observations about the structure of the graph we are working with.

Even and odd edges

Consider a non-tree edge e=(A, B). We define the tree path of the edge e to be the unique path from A to B consisting of tree edges only. If the length of the tree path is even, we say that e is an even edge; otherwise we say that e is an odd edge. We will use \operatorname{TP}(e) to denote the tree path of an edge e.

Obviously, any odd edge present in the graph together with its tree path forms an even cycle. Therefore, we can never include an odd edge in our graph and we can completely ignore them.

Relation between two even edges

Individual even edges may exist in the graph. However, if we include several even edges, an even cycle might be formed. More precisely, if e_1 and e_2 are even edges such that \operatorname{TP}(e_1) and \operatorname{TP}(e_2) share a common tree edge, then adding both e_1 and e_2 to the graph necessarily creates an even cycle.

In order to sketch the proof of this claim, consider the two odd cycles created by e_1 and e_2 together with their respective tree paths. If we remove all common tree edges from those cycles we get two paths P_1 and P_2. The parity of P_1 is equal to the parity of the P_2 since we removed the same number of edges from the two initial odd cycles. As P_1 and P_2 also have the same endpoints, we can merge them into one big even cycle.

Tree edges contained in odd cycles

As a direct consequence of the previous claim, we can conclude that every tree edge may be contained in at most one odd cycle.

Conversely, if we add only even edges to the tree in such a way that every tree edge is contained in at most one odd cycle, then we couldn't have formed any even cycles. We briefly sketch the proof of this claim here. If an even cycle existed, it would have to contain one or more non-tree edges. Informally, if it contains exactly one non-tree edge we have a contradiction with the assumption that only even edges are added; if it contains two or more non-tree edges then we will arrive at a contradiction with the second assumption.

Model solution

Now, we can use our observations to develop a dynamic programming solution for the problem. A state is a subtree of the given tree. For each state we calculate the weight of the maximum-weighted set of even edges that can be added to the subtree while maintaining the property that each tree edge is contained in at most one odd cycle. The solution for the task is the weight associated with the state representing the initial tree.

To obtain a recursive relation, we consider all even edges with tree paths passing through the root of the tree. We can choose to do one of the following:

  1. We do not add any even edge whose tree path passes through the root of the tree. In this case, we can delete the root and proceed to calculate the optimal solution for each of the subtrees obtained after deleting the root node.

  2. We choose an even edge e whose tree path passes through the root of the tree and add it to the tree. Next, we delete all tree edges along \operatorname{TP}(e) (since, now, they are contained in one odd cycle), and, finally, we proceed to calculate the optimal solution for each of the subtrees obtained after deleting the tree path. Add w(e) to the total sum.

We will use the tree in figure 1 as an example. Figure 2 shows case (1) in the recursive relation (we choose not to include an edge whose tree path passes through the root). Figure 3 shows case (2) in the recursive relation, when we include the even edge e=(7, 9) in the graph.

Because of the way the trees are decomposed, all subtrees that appear as subproblems can be represented with an integer and a bit mask. The integer represents the index of the subtree's root node, while the bit mask represents which of the root node's children are removed from the subtree.

The total number of possible states is, therefore, bounded by N\cdot 2^K where K is the maximum degree of a node. Depending on the implementation details, the time complexity of the algorithm can vary. The official implementation has time complexity \mathcal O(M \log M + MN + M\cdot 2^K).


Comments

There are no comments at the moment.