Odd Cycle Transversal, in depth: bipartization by vertex deletion, iterative compression with min vertex cuts, kernels, ILP and applications

Definitions and relatives

Testing bipartiteness is easy: breadth-first search assigns alternating colours level by level and fails exactly when an edge joins two vertices of the same colour, which closes an odd cycle. That linear-time test, covered in Bipartite Check with BFS, is the inner loop of everything below. Bipartite means 2-colourable, so OCT is the vertex-deletion distance to 2-colourability; the broader colouring problem is in Graph Colouring.

Two relatives are easy to confuse. Edge bipartization deletes edges instead of vertices; its complement is max-cut, since the edges kept are exactly a cut. Vertex cover deletes vertices to destroy every edge rather than every odd cycle; it is the special case of OCT on a graph where each edge is replaced by a triangle with a fresh vertex, which is one way to see that OCT is NP-hard. Conversely, a vertex cover of G is always an OCT, because removing it leaves an independent set, which is trivially bipartite.

Iterative compression

Iterative compression, introduced by Reed, Smith and Vetta in 2004 for exactly this problem, rests on a simple observation. Suppose you already hold a solution X that is one vertex too big, of size k+1. A compression routine either shrinks it to size k or proves no size-k solution exists. If compression runs in FPT time, the whole problem does too: add the vertices of G one at a time, keeping an OCT of the graph built so far. Adding a vertex v to a graph with OCT X gives a graph with OCT X plus v, of size at most k+1, so compress it and continue. If compression ever fails, the current subgraph has no OCT of size k, and neither does G, since a solution for G restricted to a subgraph is a solution for the subgraph.

The compression step works with three pieces of knowledge. First, the optimal solution S deletes some part Y of X and keeps the rest. Second, in the final bipartite graph each kept vertex of X sits on the left or the right. Guessing a label from {delete, left, right} for each vertex of X gives 3 to the power k+1 guesses. A guess with an edge inside the left set or inside the right set is impossible and is skipped. Third, the graph H obtained by removing all of X is bipartite, because X is an OCT, so H has a 2-colouring side(v).

Now the key step. Inside H minus whatever else we delete, each connected component can keep its colouring or flip it as a whole, and those are the only options. A vertex of H adjacent to a left vertex of X must end up on the right; adjacent to a right vertex, on the left. If that required colour equals side(v), v must keep; otherwise it must flip. So the deleted set must separate every must-keep vertex from every must-flip vertex in H. A vertex that is required on both sides is in both sets and has to be deleted itself. That is a minimum vertex cut problem, solvable with max-flow by splitting each vertex into an in-node and out-node joined by a capacity-one edge, as in the max-flow min-cut theorem. If the cut has size at most k minus the size of Y, Y plus the cut is an OCT of size k.

Counting: 3^(k+1) guesses, each a flow computation that stops after k augmenting paths of O(m) each, repeated for n vertices. Reed, Smith and Vetta stated a bound of O(4^k k m n); Hüffner's later analysis and implementation of the same approach showed O(3^k k m n).

A complete implementation

The implementation below is complete and has been checked against brute force on hundreds of random graphs with up to ten vertices and every value of k. Graphs are dicts from vertex to a set of neighbours.

from collections import deque
from itertools import product

def two_color(adj, alive):
    """BFS 2-colouring of the subgraph on `alive`; None if an odd cycle exists."""
    side = {}
    for s in alive:
        if s in side:
            continue
        side[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for w in adj[u]:
                if w not in alive:
                    continue
                if w not in side:
                    side[w] = 1 - side[u]
                    q.append(w)
                elif side[w] == side[u]:
                    return None
    return side

def min_vertex_cut(adj, alive, keep, flip, limit):
    """Smallest vertex set separating keep from flip inside `alive` (terminals deletable).
    Unit capacity per vertex, Edmonds-Karp; gives up once the cut exceeds `limit`."""
    cap = {}
    def add(u, v, c):
        cap.setdefault(u, {})[v] = cap.get(u, {}).get(v, 0) + c
        cap.setdefault(v, {}).setdefault(u, 0)
    INF = len(alive) + 1
    for v in alive:
        add((v, 0), (v, 1), 1)                 # split vertex: in -> out, capacity 1
        for w in adj[v]:
            if w in alive:
                add((v, 1), (w, 0), INF)
    for v in keep:
        add("s", (v, 0), INF)
    for v in flip:
        add((v, 1), "t", INF)
    flow = 0
    while True:
        parent, q = {"s": None}, deque(["s"])
        while q and "t" not in parent:
            u = q.popleft()
            for w, c in cap.get(u, {}).items():
                if c > 0 and w not in parent:
                    parent[w] = u
                    q.append(w)
        if "t" not in parent:
            break
        flow += 1
        if flow > limit:
            return None
        w = "t"
        while parent[w] is not None:
            u = parent[w]
            cap[u][w] -= 1
            cap[w][u] += 1
            w = u
    seen, q = {"s"}, deque(["s"])                 # residual reachability gives the cut
    while q:
        u = q.popleft()
        for w, c in cap.get(u, {}).items():
            if c > 0 and w not in seen:
                seen.add(w)
                q.append(w)
    return {v for v in alive if (v, 0) in seen and (v, 1) not in seen}

def compress(adj, alive, X, k):
    """X is an OCT of G[alive] with |X| = k + 1. Return an OCT of size <= k, or None."""
    H = alive - X
    side = two_color(adj, H)                       # H is bipartite because X is an OCT
    X = list(X)
    for labels in product("DLR", repeat=len(X)):    # D = delete, L / R = keep on that side
        Y = {x for x, l in zip(X, labels) if l == "D"}
        if len(Y) > k:
            continue
        XL = {x for x, l in zip(X, labels) if l == "L"}
        XR = {x for x, l in zip(X, labels) if l == "R"}
        if any(w in XL for x in XL for w in adj[x]) or any(w in XR for x in XR for w in adj[x]):
            continue                               # an edge inside one side: guess invalid
        keep, flip = set(), set()
        for v in H:
            need = set()
            if any(w in XL for w in adj[v]):
                need.add(1)                        # neighbour of a left vertex goes right
            if any(w in XR for w in adj[v]):
                need.add(0)
            for colour in need:
                (keep if colour == side[v] else flip).add(v)
        S = min_vertex_cut(adj, H, keep, flip, k - len(Y))
        if S is not None:
            return Y | S
    return None

def oct_iterative_compression(adj, k):
    """Return an odd cycle transversal of size <= k, or None. O(3^k * k * poly) time."""
    alive, X = set(), set()
    for v in adj:                                  # add vertices one at a time
        alive.add(v)
        X = X | {v}
        if len(X) > k:
            X = compress(adj, alive, X, k)
            if X is None:
                return None
    return X

Note that the flow lets terminals be cut: the source and sink attach to each terminal's in-node and out-node rather than bypassing its capacity-one edge.

Worked example

Take a 5-cycle 0-1-2-3-4-0 and a triangle 0-5-6 sharing vertex 0. Both cycles are odd, and they share exactly one vertex.

adj = {0: {1, 4, 5, 6}, 1: {0, 2}, 2: {1, 3}, 3: {2, 4}, 4: {3, 0}, 5: {0, 6}, 6: {0, 5}}
print(oct_iterative_compression(adj, 0))   # None: the graph is not bipartite
print(oct_iterative_compression(adj, 1))   # {0}

Trace k = 1. Vertices arrive in order 0 to 6. With 0 and 1 present, X = {0, 1} has size 2, so compression runs: the guess that deletes 0 and places 1 on the left succeeds with an empty cut, leaving X = {0}. Vertices 2, 3 and 4 each arrive, X grows to two vertices, and compression shrinks it back to {0}, because G minus 0 is still a path. Vertex 5 and then 6 arrive the same way. When 6 closes the triangle, G minus 0 is the path 1-2-3-4 plus the edge 5-6, bipartite, so {0} survives. With k = 0, the first compression that sees the 5-cycle fails, and the algorithm correctly reports no solution. Any single vertex other than 0 leaves one of the two odd cycles intact, so {0} is the unique optimum.

Beyond 3^k: faster algorithms, kernels and approximation

Further results:

• Faster FPT. Lokshtanov, Narayanaswamy, Raman, Ramanujan and Saurabh obtained O*(2.3146^k) by reducing OCT to vertex cover parameterized above its LP lower bound. The reduction takes two copies of G joined by a perfect matching between twins; this connects OCT to the matching and LP tools behind König's theorem.
• Kernels. Kratsch and Wahlström gave a randomized polynomial kernel using matroid representation: in polynomial time an instance shrinks to one whose size is polynomial in k. Kernels and the wider FPT toolbox are surveyed in Parameterized Complexity, in depth.
• Approximation. Agarwal, Charikar, Makarychev and Makarychev gave an O(sqrt(log n)) approximation using semidefinite programming. No constant-factor approximation is known.
• Integer programming. In practice, many instances are solved with an ILP: a binary variable x_v for deletion and c_v for side, with constraints forcing different sides on each surviving edge. Modern solvers handle thousands of vertices when the optimum is small and the graph is sparse.

# ILP formulation (any MILP solver): minimise sum(x[v])
# x[v] = 1 deletes v; c[v] is v's side. For every edge (u, w):
#   c[u] + c[w] >= 1 - x[u] - x[w]      # not both on side 0
#   c[u] + c[w] <= 1 + x[u] + x[w]      # not both on side 1
# x, c binary. Symmetry tip: fix c[v0] = 0 for one vertex per component.

Where OCT shows up

OCT appears wherever a system expects a two-way split and noisy data breaks it. In haplotype assembly, sequencing fragments should split into two chromosome copies; fragments that conflict are joined by edges, and fragments that make the conflict graph non-bipartite are suspected errors, a formulation studied as fragment removal. In VLSI design, assigning wires to two layers is a 2-colouring problem, and the vertices of an OCT mark where vias or rerouting are needed. In data pipelines, any set of pairwise "must differ" constraints, such as two teams in a match or A/B arms that must not share a unit, forms a graph whose OCT is the minimum number of records to drop or review to make the constraints consistent. Richer boolean constraints call for 2-SAT instead.

Pitfalls and practice

For large graphs where k is not small, practical systems combine reduction rules (remove degree-one vertices; solve connected components separately; drop edges of bipartite blocks, but never solve blocks independently, since a cut vertex like 0 in the example can serve several), an ILP or branch-and-bound on the reduced graph, and a local-search heuristic for an upper bound when the exact solver times out.

Trade-offs

What to do next

1. Implement the BFS bipartiteness test and use it as a verifier for every answer.
2. Copy the iterative compression code, run it on the worked example, then compare it with brute force on random small graphs.
3. Add reduction rules: strip degree-one vertices and solve components separately.
4. For larger instances, write the ILP above and compare running time against iterative compression as k grows.
5. Map one constraint-consistency problem in your own data to a graph and measure its OCT.
6. Read about kernels and the vertex cover above LP connection to see why OCT became a central FPT problem.