Parameterized Complexity for Structural AI Problems

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2771 papers1,036 conceptsfrozen 2026-10-04

In the traditional view of computational complexity, problems are often sorted into a binary: they are either "easy" (polynomial time) or "hard" (NP-hard). For researchers in artificial intelligence, this binary is a wall. Tasks like learning the optimal structure of a Bayesian network, finding stable equilibria in games, or disrupting covert networks are mathematically proven to be NP-hard. In the worst case, as the number of variables $n$ grows, the time required to solve them explodes exponentially.

However, real-world data is rarely "worst-case." A research direction led by scientists like Stefan Szeider, Serge Gaspers, and Fahad Panolan suggests that we can bypass this wall by looking at the structure of the problem rather than just its size. This is the core of Parameterized Complexity.

Beyond Input Size

The central intuition is that the difficulty of a problem often depends on a specific "parameter" $k$—a measure of structural complexity—rather than the total number of nodes or variables $n$. If we can isolate the exponential part of the computation to $k$, we can create algorithms that run in time $f(k) \cdot n^c$. When $k$ is small, these problems become Fixed-Parameter Tractable (FPT), meaning they are efficiently solvable even if the total dataset is massive.

In The Parameterized Complexity of Global Constraints, Emmanuel Hebrard and Toby Walsh argue that traditional analysis fails to identify these "backdoors" to tractability. By identifying natural parameters—like the number of distinct values in a domain—we can design solvers that handle complex constraints that were previously thought to be too expensive to propagate.

The Geometry of Hardness

What does this "structure" actually look like? The research identifies several recurring structural parameters that act as levers for tractability:

  • Treewidth: This measures how "tree-like" a graph or logic formula is. Trees are easy to solve because they allow for dynamic programming. Marko Samer and Stefan Szeider showed in A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth that even the daunting task of counting all satisfying assignments (#SAT) becomes linear in time if the connections between variables and clauses are sufficiently tree-like.
  • Vertex Cover: A vertex cover is a set of nodes that touches every edge in a graph. If a small number of nodes "cover" the complexity of the network, problems like frequency assignment or network disruption become manageable. Jiřı́ Fiala and Tomas Gavenciak used this to solve distance constrained labeling problems that are otherwise intractable.
  • Neighborhood Diversity: This captures symmetry. If many nodes in a network have the same neighbors, they are functionally redundant. Kamran Najeebullah demonstrated in Complexity of Optimally Defending and Attacking a Network that we can exploit these symmetries to find optimal ways to disrupt covert networks in polynomial time.

Finding Tractable Islands

This framework allows researchers to map the "tractability borderline" for high-stakes AI tasks. For example, in A Refined Complexity Analysis of Fair Districting over Graphs, Niclas Boehmer and colleagues show that while fair districting is NP-hard even on simple trees, combining structural parameters like treewidth with problem-specific parameters (like the number of districts) creates a path to exact solutions.

Similarly, in the emerging field of AI interpretability, Federico Adolfi explores the computational complexity of circuit discovery. By fixing architectural variables like network depth, we can determine if finding a "faithful" explanation of a model's behavior is actually possible or if we must settle for approximations.

The Limits of Simplification

While structural parameters offer a way forward, they are not a magic wand. Stefan Szeider points out in Limits of Preprocessing that even if a problem is FPT, we cannot always reduce it to a small "kernel" or a simplified version of itself. Some complexity is inherent and cannot be preprocessed away.

The power of this research direction lies in its precision. Instead of saying a problem is "hard," researchers like Haris Aziz and Robert Ganian are providing a "hardness map." They identify exactly which structural features—be it the branching of a preference tree or the sparsity of a Bayesian network—make a problem difficult. By understanding these structural constraints, we can build AI systems that are not just theoretically sound, but practically efficient on the specific types of data they encounter in the real world.

Papers in this version

Showing 60 of 771 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 400 papers
  2. Version 1 · 2026-10-04 · 771 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_parameterized_complexity_analysis_15be3957,
  title = {parameterized complexity analysis},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameterized-complexity-analysis/rdr_15be395768614cb78adcb08ba5e9bf14},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_parameterized_complexity_for_structural__15be3957_v1,
  title = {Parameterized Complexity for Structural AI Problems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parameterized-complexity-for-structural-ai-problems/rdr_15be395768614cb78adcb08ba5e9bf14/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}