CF 104012K - K-Shaped Figures

Rating: -
Tags: -
Solve time: 2m 6s
Verified: no

Solution

Exercise 225 constructs a ZDD whose paths encode all simple paths between two fixed vertices $s$ and $t$. The construction proceeds by a controlled search over partial edge sets: each ZDD node represents a state of the partial path, and each decision corresponds to including or excluding a candidate edge, while maintaining the invariant that the chosen edges form a simple path from the current endpoint to the target without repeating vertices.

To obtain a ZDD for all simple cycles, the essential change is that a cycle has no distinguished endpoints, while a path does. The difficulty is that a naive reduction to “paths from $v$ back to $v$” overcounts each cycle many times, once for every possible starting point and direction. The construction must therefore impose a canonical representation of each cycle while still fitting into the same state-transition framework used for paths.

The key idea is to anchor every cycle at its minimum-labeled vertex. This removes rotational symmetry and makes each cycle correspond to exactly one rooted representation. The ZDD is then built as a union over all possible anchors, where each anchored sub-ZDD enumerates cycles that start and end at the same vertex but are constrained so that no smaller vertex is ever visited.

Fix an ordering of the vertices consistent with the BDD variable ordering used in exercise 225. For each vertex $s$, define a ZDD that represents all simple cycles $C$ such that $\min(C)=s$. The final ZDD is the union over all $s$ of these structures.

Inside the construction for a fixed $s$, we modify the path ZDD from exercise 225 by replacing the terminal condition “reach $t$” with “return to $s$”, but with a strict constraint that prevents returning to $s$ before the final step. All intermediate vertices in the partial path are required to be strictly greater than $s$. This ensures that $s$ is the unique minimum vertex of every generated cycle.

The state maintained by the recursion is the same as in the path construction: the current endpoint $v$ together with the implicit set of vertices already used, represented by the ZDD path history. Transitions correspond to choosing an unused edge $(v,u)$, which is allowed only if $u$ has not appeared earlier in the path and $u > s$. The restriction $u > s$ enforces the canonical minimum condition, while the simplicity constraint ensures no vertex repetition.

A cycle is completed only when the current endpoint $v$ is adjacent to $s$ and the partial path contains at least one edge. At that moment, taking edge $(v,s)$ is allowed as a final transition to the terminal $1$ node of the ZDD. No earlier transition is permitted to enter $s$, so the closure step is unique and occurs exactly once per cycle.

Formally, for each $s$, the recursion explores all edge subsets $E' \subseteq E$ satisfying the following conditions: the subgraph $(V,E')$ is a simple cycle, $s \in V(E')$, and every $v \in V(E') \setminus {s}$ satisfies $v > s$. The ZDD structure enforces these conditions locally at each decision node by filtering admissible transitions.

Why it works

Every simple cycle has a unique vertex of minimum index under the fixed ordering. Let that vertex be $s$. Starting from $s$, traversing the cycle in either direction yields a simple path that never visits a vertex smaller than $s$ before returning to $s$. Therefore the cycle appears in exactly one of the anchored ZDDs constructed for $s$.

Conversely, any accepting computation in the anchored ZDD for $s$ produces a closed walk that starts at $s$, never revisits vertices, never leaves the set of vertices greater than $s$, and returns to $s$ exactly once at termination. These conditions force the resulting edge set to be a simple cycle with minimum vertex $s$.

Thus each simple cycle corresponds to exactly one accepting path in exactly one anchored ZDD, and every accepting path corresponds to exactly one simple cycle. This establishes a bijection between cycles in the graph and solutions represented by the final ZDD construction. This completes the proof. ∎