Decomposing QUBO Optimization at Vertex Separators
Motivation
This work is motivated by hardware virtualization, a problem arising in the use of quantum annealers and other special-purpose Ising solvers. A quantum annealer can accommodate only problems that fit its fixed, sparse connectivity and its finite qubit budget. If a large QUBO could be divided at a separator, each part solved within the available capacity, and the parts recombined without loss, then problems exceeding the capacity of a single device could still be solved, either in parallel across several devices or serially on one.
The goal, then, is to find the separator strategies that best divide such a problem, so that its optimum can be recovered exactly from the independently solved pieces.
The interaction graph and its separators
Each problem we want to solve is one instance of QUBO, or equivalently of the Ising model. An instance is a set of binary variables together with the numbers that define its objective: a bias h_i attached to each variable, and a coupling J_ij between certain pairs of variables. Solving the instance means choosing a value for every variable so that this objective is as small as possible.
Every instance has a natural representation as a weighted graph G = (V, E). Each node in V is one variable, and an edge (i, j) joins two variables whenever they interact through a nonzero coupling J_ij. The bias h_i is stored on node i, and the coupling J_ij on edge (i, j). This graph is the interaction graph, and it is what every strategy below operates on.
A vertex separator is a set of nodes S ⊆ V whose removal splits the remaining graph into two parts A and B with no edge joining A to B: every path from A to B passes through S. Because no edge crosses directly from A to B, the two parts interact only through the separator, and that is precisely the property that admits decomposition. The six strategies below each show a worked example (the cut its finder actually computes), with the separator S in red and the two parts A and B in blue and green.
Conditioning: how a separator decomposes the problem
Fix the separator variables to a specific assignment. Every coupling from a separator node into A then contributes a constant that folds into the bias of its A-neighbour (and likewise for B). With the separator held fixed, A and B share no variable and no edge, so each is an independent, smaller QUBO. The exact minimum for that separator assignment is
E_S(fixed) + min over x_A of E_A(x_A | fixed) + min over x_B of E_B(x_B | fixed),
where E_S(fixed) collects the separator’s own internal terms. Enumerating the 2^|S| assignments of S and keeping the smallest total gives the exact global optimum.
The cost is therefore ≈ 2^|S| · (cost of A + cost of B). The exponent is the separator size, so a small, balanced S is decisive: it both shrinks 2^|S| and splits the remaining work into two comparable halves.
Applied recursively (each part is itself cut at a separator, and so on), this produces a binary tree of cuts. That recursion is nested dissection, specialized here to Ising ground states.
One important point remains. Finding the smallest balanced separator is itself NP-hard, so every strategy below only searches for a good S; it does not guarantee the best one. Correctness, however, does not depend on that search succeeding. Every proposed cut is first checked: it must be a real split, with both parts non-empty and no edge crossing from one part to the other. Only a cut that passes this check is used, and the recombination that follows is exact. A weak search therefore yields a larger separator, and hence a larger 2^|S|, but never a wrong answer. A cut wider than a fixed limit (about twenty separator nodes) is refused, and the block is kept whole.
One Recombination, Six Ways to Cut
The recombination above is fixed: condition on the separator, solve the two parts, recombine, recurse. The strategies differ only in how they locate the separator. A dispatcher runs all six on the interaction graph, validates each candidate, and keeps the smallest, most balanced feasible cut.
Separator 1: Flow
The Flow strategy computes a true minimum vertex separator between a chosen source and sink by the classical vertex-splitting max-flow construction: split each node into an in/out pair of unit capacity, route each edge at infinite capacity, and read the minimum cut (Menger’s theorem). It tries several far-apart source/sink pairs and keeps the smallest balanced cut. It is the strategy of choice on any well-connected graph, since it returns the genuinely minimum boundary.
The graph below is a random 15-node graph. The Flow strategy searches over source/sink pairs; its winning pair is source node 9 and sink node 10. Between them, the minimum balanced vertex cut is the five-node separator S = {4, 5, 8, 11, 12} (red), the smallest set of nodes whose removal separates the source from the sink. It splits the graph into two parts A and B of five nodes each, with no edge crossing between them.
Separator 2: Layout
The Layout strategy is the general fallback. It imposes no structural requirement on the graph and applies to any family, deferring to the more specialized finders only when one of them returns a smaller cut. It proceeds in two stages. First it fixes a linear arrangement of the nodes: a single left-to-right ordering along a line that assigns each node an integer position. The arrangement is constructed to keep the graph bandwidth low, the bandwidth being the greatest distance, measured along the line, spanned by any edge. In a low-bandwidth arrangement every edge therefore joins two nodes that lie close together, and no edge reaches far across the line. Second, it scans that arrangement for the cheapest position to cut, as described below.
The arrangement comes from a reverse minimum-fill elimination order. This order is computed deterministically, with no randomness. It is built greedily, one node at a time. At each step the strategy removes a single node. It picks the node whose removal adds the fewest fill edges, the new edges needed to keep that node’s neighbours connected once it is gone. The removed node is appended to the order, the fill edges are added, and the step repeats until every node is placed. Reversing this order gives the linear arrangement.
To locate the separator, the strategy evaluates every cut position along the arrangement. A cut at position c places the nodes with position below c in a left part A. The separator S is the right-side boundary of the cut: every node at position c or beyond that still has a neighbour in A. The remaining right-side nodes, having no neighbour in A, form B. By construction every edge leaving A must terminate in S, so no edge joins A to B and S is a valid separator. Each candidate cut is scored by separator size first, then by the size of the larger part, then by cut position, and the smallest, most balanced cut is kept. Because every boundary node is reached by an edge no longer than the bandwidth, |S| never exceeds the arrangement’s bandwidth. A cut is rejected when either side is empty or the separator is almost the whole graph (|S| ≥ n − 1); if no cut survives (as on a near-clique or expander, whose only separators are near-total), the strategy declines and the block is kept whole.
The example below is a small random geometric graph of eight nodes. Its spatial locality gives it a low-bandwidth arrangement, so the strategy finds a clean cut: a two-node separator S (red) that splits the graph into two three-node parts A and B.
The next figure redraws the same graph along its reverse minimum-fill order, left to right, with the cut marked by the dashed line. Everything left of the cut is part A (blue). The separator S (red) is the two nodes just right of the cut that still have an edge reaching back into A. Part B (green) is the rest of the right side, and no edge from B crosses back over the cut. The arcs make the rule visible: exactly the two edges that span the cut land in S, so nothing joins A to B directly.
Separator 3: Block-cut
The Block-cut strategy returns an articulation point: a single node whose removal disconnects the graph, giving a separator of size 1. The strategy finds every articulation point of the graph and keeps the one whose removal splits it most evenly. A minimum-cut search can overlook such a node, since its source/sink trials need not straddle it, yet an articulation point is the cheapest possible cut whenever one exists.
The graph below is two K₅ cliques joined through a single middle node: one edge runs from that node to one node of each clique. The middle node (red) is an articulation point: removing it disconnects the two cliques, so the separator is that one node, the cheapest cut possible.
Separator 4: Series-parallel
A series-parallel graph is built up from single edges using two operations. A series operation joins two pieces end to end, so they meet at one shared node and form a longer chain. A parallel operation glues two pieces together at both endpoints, so they run side by side between the same two nodes. Any graph built this way has treewidth at most two (equivalently, it has no K₄ minor). As a consequence, whenever such a graph can be separated at all, a separator of at most two nodes suffices.
To locate the separator, the strategy first verifies that the graph is series-parallel; if it is not, the strategy declines and defers to another finder. Once series-parallel structure is confirmed, the treewidth-two property means that if the graph can be separated, a set of at most two nodes suffices, and the strategy searches for that set exhaustively. It first evaluates each node individually, determining whether its removal alone disconnects the graph into two parts, a one-node separator. It then evaluates every pair of nodes, determining whether their joint removal disconnects the graph, a two-node separator. For each candidate, the strategy removes the node or the pair, partitions the remainder into the two parts A and B, and verifies that the partition is valid: both parts non-empty, with no edge joining A directly to B. Among all valid cuts it retains the most balanced, ranked by the size of the larger part with a deterministic tie-break. The search is exhaustive yet inexpensive, since a graph of n nodes admits only n single-node candidates and approximately n² two-node candidates. If no valid cut exists, as for a small clique that cannot be separated at all, the strategy declines.
Searching the candidate cuts directly, rather than reading a cut position from a linear arrangement, allows the strategy to locate the central separator. The Layout strategy’s bandwidth ordering may place a two-node cut near one end of the graph, producing a lopsided split; the direct search instead identifies the balanced cut at the middle.
The graph below is a ladder of six rungs (a 2 × 6 grid), which is series-parallel (treewidth 2), so a separator of at most two nodes exists. The strategy searches for the most balanced such cut and returns two nodes (red) that split the ladder into two equal halves, A and B.
Separator 5: Cograph
The Cograph strategy first determines whether the interaction graph is a cograph, and locates a separator only once that structure is confirmed. A cograph is a P₄-free graph, one containing no induced path on four nodes. Equivalently, every cograph is assembled from single nodes by two operations: a disjoint union, which places two cographs side by side with no edge between them, and a join, which places two cographs side by side and adds every possible edge between them. Recognition proceeds by modular decomposition and mirrors this construction: a disconnected graph is the disjoint union of its components, a graph whose complement is disconnected is the join of the corresponding parts, and a graph that is neither connected nor the complement of a connected graph contains an induced P₄ and is therefore not a cograph. When recognition fails, the strategy declines and leaves the cut to another finder.
Cographs form a broad and structurally important family. They include every complete graph K_n, every complete bipartite graph K(a, b), and every threshold graph. These are dense, highly regular structures on which a minimum-cut or bandwidth search performs poorly. It is precisely on such graphs that the modular structure of a cograph exposes a separator the other strategies overlook.
Recognition produces a cotree: a tree whose leaves are the individual nodes and whose internal nodes are each labelled union or join, recording the order in which the graph was assembled. Every node of the cotree spans a module, a set of nodes M that share exactly the same neighbours outside M, so that every node not in M is adjacent either to all of M or to none of it. This property makes a module’s boundary a clean separator. Its external neighbourhood S = N(M) is the set of outside nodes adjacent to M; because no other outside node touches M, deleting S detaches M from the remainder entirely.
To locate the separator, the strategy walks the cotree and enumerates every module. For each module M that is neither a single node nor the whole graph, it forms the candidate cut A = M, S = N(M), and B equal to the remaining nodes, and verifies that the split is valid. Among all valid candidates it retains the most balanced, ranked by the size of the larger part and then by the size of the separator.
The example below is a small cograph of eight nodes: a two-node core (red) joined to every node of two separate triangles, which themselves share no edge. The core is the external neighbourhood of each triangle, so removing it detaches the two triangles from one another; the Cograph strategy returns the core as the separator S, with the triangles as parts A and B. Notably, neither core node is an articulation point on its own (deleting one still leaves the other joined to both triangles), so the Block-cut strategy finds nothing here. Only the module boundary reveals the cut.
The cotree of this graph records exactly how it is assembled and makes the modules explicit. Its leaves are the eight nodes, labelled as in the figure above.
Each triangle sits under its own subtree (a module), while the root join attaches the core to both triangles at once. Because the two triangles meet only through that join, the core is their shared external neighbourhood S, and cutting it separates them.
Separator 6: Cell (Selby)
The Cell strategy applies to any graph with a quotient cell structure. In such a graph the nodes fall into groups that share a neighbourhood: every member of a group has the same neighbours outside it, so the members are interchangeable. Pairs of groups joined by a complete bipartite graph form cells, the dense biclique connections that give the family its name, and any remaining sparse edges are residual. The strategy generalizes the Hamze–Freitas–Selby subgraph solver; the detection itself is topology-agnostic and fires on any clustered or block-structured graph, such as biclique lattices or graph blow-ups.
Rather than recurse, the strategy works by reduction and lifting. It first detects the groups by neighbourhood equivalence and contracts each group into a single super-node, producing a small quotient graph whose nodes are the groups and whose edges are the cells and residual connections between them. Because the quotient is far smaller than the original, its separators are cheap to find: the strategy locates a balanced separator of the quotient by reusing the general finders: the Flow and Layout cuts, every layout cut position, and a set of breadth-first cuts grown from peripheral groups. It then lifts the chosen quotient separator back to the original graph: the separator is the union of the nodes in the separator groups, and the two parts A and B are the nodes of each part’s groups. Because residual edges can cross group boundaries, each lifted cut is re-validated against the original graph and discarded if a residual edge would join A to B. The most balanced valid lift, within the separator-size cap, is kept.
This reduction is the strategy’s advantage. The quotient’s treewidth is far below the raw graph’s, so a balanced cut of the quotient yields a balanced cut of a graph that the general finders, working directly on the raw nodes, would bisect only along a long, unbalanced spine.
The example below is a small cell-structured graph: a “blown-up path” of five groups, each a pair of twin nodes with the same neighbourhood, where consecutive groups are fully joined by a biclique cell (a complete bipartite K(2, 2)). Contracting each group to a super-node gives a five-node path; its middle super-node is the balanced separator of the quotient, which lifts back to the two nodes of the middle group (red, S), separating the two left groups (A) from the two right groups (B). On a one-dimensional chain like this the Flow strategy happens to find the same cut; the Cell strategy earns its place on two-dimensional cell grids, where the quotient exposes a balanced bisection that the one-dimensional cuts cannot.
The strategy never operates on the ten nodes directly. It contracts each group of twin nodes into a single super-node and works on the resulting quotient, which for this graph is a five-node path:
Every edge of this quotient is a biclique cell of the original graph. Separating the path is immediate (its middle super-node is the balanced cut), and lifting that super-node back to its two nodes {4, 5} recovers the separator S on the full graph.
Solving the pieces
The separator recursion reduces the problem to indivisible leaf pieces: parts small enough, or already cut down enough, that no useful separator remains. Each leaf is handed to a pluggable part-solver: an exact solver on small pieces (brute-force enumeration, or bounded-treewidth variable elimination, either of which certifies the leaf optimum), or a heuristic solver on pieces that remain large and dense. The nested-dissection recombination around them is exact in either case; the choice of part-solver affects only whether each leaf is solved exactly, not whether the pieces are recombined correctly.
Conclusion
The six strategies share a single, exact recombination: condition on a separator, solve the two parts independently, and recombine by nested dissection. They differ only in how they locate that separator, each exploiting a different structural feature: a minimum vertex cut, a low-bandwidth linear arrangement, an articulation point, a series-parallel decomposition, a cograph’s modular boundary, or a cell quotient. Because correctness rests entirely on the recombination, and every candidate cut is validated before use, the framework is open by construction: any new finder that returns a genuine separator plugs in alongside the others, competes on balance and separator size, and cannot compromise exactness: a better heuristic only yields a cheaper cut, never a wrong answer.
That openness is also an invitation. The list of six is not meant to be exhaustive; each strategy earns its place by recognizing a graph family the others handle poorly, and other families surely admit cheaper separators still. If you know of a graph structure whose separators these strategies miss, or a finder that would locate them, we would be glad to hear about it.