---
title: "Hypergraph bisection"
description: "Build a contraction tree by recursively partitioning the tensor hypergraph, using dynamic programming for small subproblems."
eyebrow: "Path-search algorithms"
---

## Building a contraction tree by partitioning {#bisect}

Hypergraph bisection treats tensors as vertices and shared indices as hyperedges connecting the corresponding vertices. It partitions the vertices into two groups, processes each recursively, then contracts the two results.

An ordinary edge connects two vertices; a hyperedge may connect more than two. If one index occurs in three tensors, a single hyperedge connects all three. The partition determines which tensors are contracted within each group before the two groups are combined.

```diagram
tensor-partition-routes
The dashed line marks the partition boundary. Orange hyperedges connect nodes on both sides. Each crossing hyperedge is counted once, regardless of the number of endpoints.
```

Subject to group-size constraints, the partition aims to minimize the weighted sum of hyperedges crossing between groups:

$$
\operatorname{cut}(L,R)=
\sum_{\substack{e\cap L\ne\varnothing\\e\cap R\ne\varnothing}}
\log_2 d_e.
$$

$d_e$ is the dimension of the corresponding index. This partition cost is not the FLOPs or memory traffic of the complete path. Partitioning only determines the contraction tree; it **neither removes indices nor performs slicing**.

## Recursive process {#recursion}

First partition a smaller hypergraph formed by coarsening vertices, then expand and refine the partition level by level. Repeat on each side; when the vertex count is at most `cutoff`, switch to [subset dynamic programming](/docs/structured-search#optimal-dp).

```pseudocode
Build subtree(S):
    if S contains only one tensor:
        return that tensor
    if the number of tensors in S <= cutoff:
        return the local tree found by subset DP
    (L, R) = bisect hypergraph S
    left = build subtree(L)
    right = build subtree(R)
    return the tree obtained by merging left and right
```

Different random seeds and balance parameters produce different candidates. After multiple trials, choose by the objective value of the complete path. Process disconnected components separately, then combine them by outer product in size order.

## Interfaces {#interfaces}

`bisect` uses the default objective; `bisect_with_objective` lets you specify the objective used to compare complete candidates. For small subproblems, `optimal_dp` still uses the default objective $F+64R$, not the caller-supplied weights. `cutoff` must be between 2 and 20; see the signatures in the [Rust API](/docs/rust-api#bisect).

Bisection is a heuristic and does not guarantee a globally optimal path. Light uses bisection candidates; Heavy does not. See [Light / Heavy interfaces](/docs/auto-light-heavy).