Scaling Combinatorial Optimization via Graph Decomposition

70 concepts66 papers2 proposals

Many real-world problems—ranging from resource allocation and computer vision to financial portfolio design and logical reasoning—are fundamentally NP-hard. When treated monolithically, their computational complexity scales exponentially or multiplicatively with the number of decision variables. However, these massive problems are rarely uniformly dense. Instead, the interactions between variables often form a sparse network. By mapping these interactions to a graph, we can exploit topological structures to decompose a single intractable problem into a collection of smaller, independent, or loosely coupled subproblems.

From Multiplicative to Additive Complexity

To understand why graph-based decomposition works, consider the search space of a global optimization problem. If a problem with $N$ binary choices cannot be broken down, a solver must navigate a space of $2^N$ possibilities. But if the variables can be partitioned into two completely independent sets of size $N/2$, the search space drops from $2^N$ (a multiplicative relationship) to $2^{N/2} + 2^{N/2}$ (an additive relationship).

This insight was leveraged by Tuomas Sandholm in An Algorithm for Optimal Winner Determination in Combinatorial Auctions. In combinatorial auctions, bidders compete for bundles of items. By treating bids as nodes and drawing edges between bids that share items, the global auction can be represented as a conflict graph. Preprocessing steps can then isolate disjoint sub-markets that do not share any items, allowing the winner determination problem to scale efficiently to large datasets.

Similarly, in A Faster Core Constraint Generation Algorithm for Combinatorial Auctions, the authors demonstrated that identifying independent clusters of bidders and items through a bipartite conflict graph allows an iterative solver to generate multiple non-overlapping constraints simultaneously. This structural awareness transforms a single large optimization task into several smaller updates, drastically reducing the total number of iterations required to reach an optimal solution.

Exploiting Structural Bottlenecks: Articulation Points and Bridges

A graph does not need to be completely disconnected from the start to benefit from decomposition. Often, a large network is held together by a few critical nodes or edges known as articulation points (or cut-vertices) and bridges. Removing an articulation point or a bridge splits the graph into independent connected components.

In Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations, Tuomas Sandholm et al. showed that detecting articulation points within a bid graph enables the decomposition of complex optimization problems into independent subproblems. This approach significantly reduces computational overhead in sparse environments by solving smaller, isolated components rather than a single massive problem.

This concept applies directly to physical infrastructure networks as well. For instance, Joan Vendrell et al. developed a framework in FORWARD: Feasibility Oriented Random-Walk Inspired Algorithm for Radial Reconfiguration in Distribution Networks that identifies articulation points to partition large power or water distribution networks into independent sub-graphs. This divide-and-conquer strategy transforms a single complex combinatorial problem into multiple smaller tasks, facilitating scalability for large-scale infrastructure applications.

Bridges provide a similar leverage point. In hardware design, Bei Yu et al. demonstrated in Layout decomposition for triple patterning lithography that exploiting bridges within a conflict graph allows for the independent partitioning of layout decomposition tasks without loss of optimality. By rotating color assignments within partitioned sub-graphs, designers can resolve boundary conflicts without the need for additional mask stitches, facilitating more efficient parallel processing.

This structural divide-and-conquer strategy is formalized by Jingming Hu in BC tree-based spectral sampling for big complex network visualization, where decomposing a graph into biconnected components via block cut-vertex trees isolates local connectivity patterns from the global topology, enabling massive parallel speedups.

Recursive Processing via Strongly Connected Components

When dealing with directed graphs—such as logical argumentation frameworks or sequential voting rules—the natural analogue to connected components is the Strongly Connected Component (SCC). An SCC is a maximal subgraph where every vertex is reachable from every other vertex. Because dependencies between different SCCs are unidirectional, the components form a directed acyclic graph (DAG), which can be processed sequentially or recursively in topological order.

This recursive meta-algorithm has significantly advanced formal AI reasoning. Pietro Baroni et al. showed in Computational Properties of Resolution-based Grounded Semantics that SCC decomposition partitions complex argumentation graphs into smaller, independent subgraphs for localized analysis, simplifying the computation of argument extensions.

Building on this, Federico Cerutti et al. introduced PrefSat in An SCC Recursive Meta-Algorithm for Computing Preferred Labellings in Abstract Argumentation, demonstrating that decomposing massive argumentation graphs into smaller, isolated sub-frameworks allows local SAT solver instances to run recursively, overcoming monolithic scalability bottlenecks. As highlighted by Federico Cerutti et al. in the Summary Report of The First International Competition on Computational Models of Argumentation, this graph-theoretic optimization consistently outperforms pure search-based methods by isolating sub-problems and reducing the overall computational search space.

The same principle applies outside of logic: Jun Wang et al. applied SCC decomposition to multi-stage voting rules in Practical Algorithms for Multi-Stage Voting Rules with Parallel Universes Tiebreaking, reducing the exponential complexity of global tie-breaking searches by solving localized segments independently.

Decomposing Interconnected Systems: Communities and Cuts

In many real-world applications, graphs are not perfectly separable by bridges or articulation points. Instead, they exhibit a "community structure"—dense clusters of highly interacting variables that are only weakly connected to other clusters. In these cases, algorithms use graph partitioning, minimum cuts, or modularity optimization to force a decomposition.

For instance, in large-scale financial applications, Atithi Acharya et al. developed a pipeline in Decomposition Pipeline for Large-Scale Portfolio Optimization with Applications to Near-Term Quantum Computing that identifies modular communities within a variable interaction graph. Solving these clusters independently preserves significant local interactions while reducing the computational burden of NP-hard portfolio optimization.

Similarly, Yunfeng Yang et al. utilized graph-theoretic modularity optimization in New Online Tuning Methods for Power System Stabilizer Parameters Based on D-segmentation Method to decompose large power grids into independent subsystems, minimizing inter-regional coupling and allowing local optimization within highly connected clusters.

When boundaries must be cut, dual variables or minimum-cut algorithms ensure that the decomposition minimizes the loss of global accuracy. Chin-Yao Chang et al. showed in Convex relaxation for mixed-integer optimal power flow problems that using dual variables from a convex relaxation to weight edges allows for network partitioning that minimizes the loss of global optimality, enabling parallel solving of large-scale systems.

In social network planning, Aye Phyu Phyu Aung et al. leveraged minimum-cut algorithms in We Mind Your Well-Being: Preventing Depression in Uncertain Social Networks by Sequential Interventions to partition global graphs into manageable sub-clusters, computing optimal intervention policies independently before aggregating them into a global policy.

Why It Works: The Power of Localized Solvers

Ultimately, graph-based problem decomposition works because it aligns the structure of the computational solver with the physical or logical structure of the data. By isolating local density hotspots—whether they are fully connected cliques in Gaussian graphical models (Yi-Cheng Chen et al.), vertex-centered subgraphs in bipartite networks (Jiajie Xu et al.), or disjoint paths in evacuation networks (Andreas Schutt)—researchers can deploy specialized exact solvers on small, manageable partitions. Rather than forcing a single monolithic solver to choke on a massive global problem, graph decomposition transforms the challenge into a highly parallelizable, additive task, unlocking new scales of efficiency across diverse scientific domains.

Key Foundational Work

Improved Algorithms for Optimal Winner Determination in Combinatorial Auctions and Generalizations (2000) — contributed 2 concept elements to this direction.
An Algorithm for Optimal Winner Determination in Combinatorial Auctions (1999) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_problem_decomposition_070e967e,
  title = {graph-based problem decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-problem-decomposition/rdr_070e967e97ff478c9955cc722f690bcf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_problem_decomposition_070e967e_v1,
  title = {graph-based problem decomposition},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-problem-decomposition/rdr_070e967e97ff478c9955cc722f690bcf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake