# On decomposing a graph into cycles

## Undirected edge-disjoint cycles
There is a nice [theorem](https://en.wikipedia.org/wiki/Veblen's_theorem) that states that the edges of a graph can be decomposed into a set of edge-disjoint cycles iff every node has even degree. In other words, for every edge, make it part of exactly one cycle. If we know this is true, we can just repeatedly remove a cycle: removing any cycle keeps all degrees even. How do we find a cycle? Just DFS, and return as soon as you have found a cycle. Note that the condition for finding an euler cycle is almost exactly the same; the only extra requirement is connectedness.

Some implementation details: you don't want to waste time potentially looping through nodes that have become degree 0. Therefore, keep DFSing from each node until we stop finding cycles:

def dfs(i,...) -> return true of a cycle was found, false otherwise

for i in range(n):
    while dfs(i,...):
        pass

The next annoying part of the algorithm is that we need to be able to delete the edges in our cycle from the graph. It's easy to delete the edge from the side we are on, but remember that the edges are undirected, so we need to delete the "other side" of the edge. The slower method is to use sets:

def dfs(u: int, adj: list[set[int]]):
    while len(adj[u]):
        e = next(iter(adj[u]))
        adj[u].erase(e)
        adj[e].erase(u)
        ...

To speed it up (needed for 100p on postmen), for each edge, assign it a unique index, that is the same for both sides of the edge. We will now lazily delete edges; we will mark them as deleted, and when we access it, we check if it's been deleted, and if so, discard it. This results in $O(M)$ work overall. This method of lazily deleting items is very useful and generalizes to more advanced data structures.

deleted = [False] * m
def dfs(u: int, adj: list[set[int]]):
    while len(adj[u]):
        e,ind = adj[u][-1]
        del adj[u][-1]
        if deleted[ind]:
            continue
        deleted[ind]=True
        ...

Problems:
- [BOI 2014 postmen](https://oj.uz/problem/view/BOI14_postmen)
- [NOI 2020 christmas gifts](https://open.kattis.com/problems/christmasgifts)

## Directed edge-disjoint cycles
In the directed case, a similar theorem applies: the requirement is that every node has equal indegree and outdegree. Similarly, the added requirement for an euler cycle is once again strong connectivity.

Pretty much the exact same algorithm we used for the undirected case will work for the directed case.

## Directed/undirected node-disjoint cycles
Let's solve the more general directed case. The undirected case is simply a special case of solving it for directed graphs (split every undirected edge into two directed ones). Note that this might gives you lots of cycles of length 2. There is no way to prevent without NP time.

The idea now is as follows: we want to select a subset of edges such that every node has indegree=outdegree. By the previous theorem, we will have a set of cycles, and because every node has nonzero degree, we have a solution. Another way to think of this is that every node chooses some edge to continue to. Suppose we are working with this graph

Which has the following solution
So the goal is for every node to have indegree and outdegree 1. This sounds familiar to bipartite matching, where the goal is for every node to get degree 1.

We will build a bipartite graph. Split every node into two parts: the one that chooses the edge goes from and the one that receives it. For each edge $u \rightarrow v$, add the edge $u_{out} \rightarrow v_{in}$ in the bipartite graph.

Now, what did we want again? Select a set of edges such that the indegree and outdegree of each node = 1 in the original graph. This is equivalent to choosing edges in this bipartite graph such that every node has degree 1. This is exactly the problem of finding a perfect matching!

The only perfect matching is marked in red, corresponding to the solution drawn above. Note that if the matching is not perfect, we cannot say anything about our solution; it might consist of disjoint paths.

This solution can generalize in several ways. If the edges are weighted, we can easily use weighted bipartite matching. Additionally, many similar problems related to path and cycle covers can be solved similarly.

Problems:
- https://open.kattis.com/problems/sightseeing

## Optimization version of edge-disjoint cycles
Suppose instead that we want to select the largest edge-disjoint set of edges that decomposes into a set of cycles. Note that we cannot say *anything* about the number of cycles; then it becomes NP (hamiltonian cycle). In one sentence, this can be solved as an instance of min-cost circulation, where every edge has capacity 1 and cost -1. I will now give you an introduction to how to get there; this will serve mostly as a glance into the world of flows, and the fact that it's not simply only max flow.

Let's formalize our problem: for each edge, create a binary variable $e_i$, which is $1$ if it's used, otherwise $0$.

Our problem can now be stated as follows: we want to maximize

$$\sum_{i=0}^{n-1} e_i$$

We have the constraints

$$0 \leq e_i \leq 1$$

It could of course also be written as $e_i \in \{0,1\}$. However, it turns out that min cost circulation can easily handle upper bounds that are larger than $1$, so let's keep said form for sake of generality. Finally, we also need to ensure that every node has equal indegree and outdegree (recall the theorem that this implies we can get a set of edge-disjoint cycles):

$$\sum_{a \rightarrow v} e_i - \sum_{v \rightarrow b}e_i=0 \hspace{0.5em}\forall v$$

Now, to solve this, we could iterate over all $2^m$ ways to assign values to $e_i$. This is obviously too slow. We might notice that everything is linear and turn to [integer linear programming](https://en.wikipedia.org/wiki/Integer_programming). Unfortunately, this is NP (it can solve knapsack). However, our set of constraints is special; as it turns out, all optimal solutions will be integers (our constraints are so-called [totally unimodular](https://en.wikipedia.org/wiki/Unimodular_matrix#Total_unimodularity)). So one way to solve the problem is to simply run your favorite linear programming solver like simplex (although this is slow). The way to actually solve this using an algorithm known as [network simplex](https://codeforces.com/blog/entry/94190), which is interesting, but pretty advanced. This optimization problem is deeply linked to max flow [^1]. One way to think of it is that max flow finds paths, while this finds cycles. This exact problem we have is known as [min-cost circulation](https://en.wikipedia.org/wiki/Circulation_problem), and is in some circles regarded as the only relevant flow problem; max flow and min-cost max flow are special cases of it.

Because of the previously-mentiond NP result, for the directed case, we cannot do anything better than splitting every undirected edge into two directed edges.

Problems:
- https://open.kattis.com/problems/chainslides

## Optimization version of node-disjoint cycles
For this version, we can reuse the previous solution with a classical flow trick: split every node into two parts, one for the in-edges and one for the out-edges.


By setting the middle edge's capacity to 1, we have essentially added the constraint "at most 1 cycle may pass through this" node. By running min-circulation, we find node-disjoint cycles.

[^1]: In fact, max flow can be solved using this optimization problem: simply add an edge sink -> source with infinite capacity and cost -1.