arxiv: 2601.16156 · v2 · submitted 2026-01-22 · 💻 cs.DM · cs.DS

Recognition: 2 theorem links

· Lean Theorem

All ascents exponential from valued constraint graphs of pathwidth three

Artem Kaznatcheev , Willemijn Volgering

Authors on Pith no claims yet

Pith reviewed 2026-05-16 11:47 UTC · model grok-4.3

classification 💻 cs.DM cs.DS

keywords valued constraint satisfactionpathwidthlocal searchfitness landscapeexponential lower boundsconstraint graphspseudo-Boolean optimization

0 comments

The pith

Valued constraint graphs of pathwidth three can force all ascents to be exponentially long from a given start.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds a valued constraint satisfaction problem whose underlying constraint graph has pathwidth exactly three. From one fixed starting assignment, every sequence of strictly improving flips must take an exponential number of steps before reaching a local optimum. This improves on earlier constructions that required pathwidth at least four to achieve the same exponential lower bound. The result shows that the sparsity level captured by pathwidth three is still enough to encode fitness landscapes on which strict local search is forced to run for exponential time. A sympathetic reader therefore concludes that pathwidth alone does not guarantee efficient local search.

Core claim

We give a controlled doubling construction that yields a valued constraint satisfaction problem of pathwidth three such that, from a designated initial assignment, every improving move sequence has length exponential in the size of the instance.

What carries the argument

controlled doubling construction, which iteratively doubles the length of ascent paths while keeping the constraint graph at pathwidth three

If this is right

Strict local search algorithms require exponentially many steps on some instances whose constraint graphs have pathwidth three.
Pathwidth three does not suffice to place a polynomial upper bound on the length of ascents in the fitness landscape.
Exponential lower bounds for local search extend to the smallest pathwidth previously thought to allow only short ascents.
Any algorithm that relies on following improving moves will take exponential time on the constructed family of instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same doubling technique might be adapted to show exponential ascents under other sparsity measures such as treewidth two or bandwidth three.
Local-search heuristics for problems on pathwidth-three graphs may require restarts or lookahead to avoid long ascent paths.
The construction separates the complexity of following improving moves from the complexity of finding a global optimum.

Load-bearing premise

The controlled doubling construction produces a graph whose pathwidth is exactly three while making every improving sequence from the chosen start exponentially long.

What would settle it

An explicit polynomial-length improving sequence from the designated start in the constructed instance, or a formal proof that every pathwidth-three constraint graph admits a short ascent from any assignment.

Figures

Figures reproduced from arXiv: 2601.16156 by Artem Kaznatcheev, Willemijn Volgering.

**Figure 1.** Figure 1: Gadget C MT k of Monien and Tscheuschner construction [29] (C MT) with constraint weights omitted. Dotted edges and vertices illustrate connections to neighboring gadgets. Node labels refer to grid position in layout of [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗

**Figure 2.** Figure 2: Gadget C MS k of Michel and Scott construction [28]: the weights of unary constraints are next to their variables and the weights of binary constraints are on the edges that specify their scope. The dotted edges and vertices illustrate the connection to the neighboring gadgets. 7 [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Figure 3: A gadget C CD k of the controlled doubling construction with mk = 2k−1 (8n + 16) − 16 and sk = 8(n − k). The constraints of the kth of n gadgets are shown: the weights of unary constraints are next to their variables, the weights of binary constraints are on the edges that specify their scope, the weights of ternary constraints are in the center of the shaded area that specify their scope. The dotted edges… view at source ↗

**Figure 4.** Figure 4: The first gadget (C CD 1 ) of the controlled doubling construction with m1 = s0 = 8n. The constraints of the first gadget are shown: the weights of unary constraints are next to their variables, the weights of binary constraints are on the edges that specify their scope, the weights of ternary constraints are in the center of the shaded area that specify their scope. The dotted edge and vertices illustrate… view at source ↗

read the original abstract

Many combinatorial optimization problems can be formulated as finding an assignment that maximizes some pseudo-Boolean function (that we call the fitness function). Strict local search starts with some assignment and follows some update rule to proceed to an adjacent assignment of strictly higher fitness. This means that strict local search algorithms follow ascents in the fitness landscape of the pseudo-Boolean function. The complexity of the pseudo-Boolean function (and the fitness landscapes that it represents) can be parameterized by properties of the valued constraint satisfaction problem (VCSP) that encodes the pseudo-Boolean function. We focus on properties of the constraint graphs of the VCSP, with the intuition that spare graphs are less complex than dense ones. Specifically, we argue that pathwidth is the natural sparsity parameter for understanding limits on the power of strict local search. We show that prior constructions of sparse VCSPs where all ascents are exponentially long had pathwidth greater than or equal to four. We improve this this with our controlled doubling construction: a valued constraint satisfaction problem of pathwidth three where all ascents are exponentially long from a designated initial assignment. We conclude that all strict local search algorithms can be forced to take an exponential number of steps even on simple valued constraint graphs of pathwidth three.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives an explicit controlled-doubling construction for a pathwidth-three VCSP that forces every strict local-search ascent from a fixed start to be exponentially long.

read the letter

The main takeaway is that the authors supply a concrete construction, called controlled doubling, that produces a valued constraint satisfaction problem whose constraint graph has pathwidth exactly three yet requires exponentially many improving flips from a designated initial assignment. This lowers the known threshold for forcing exponential local-search time on sparse graphs from four down to three. The manuscript includes an inductive definition of the instance together with an explicit path decomposition that keeps the width at three and a potential-function argument that rules out short ascents. Those two pieces are shown to hold simultaneously without one undermining the other. The paper situates the result cleanly against earlier constructions that needed higher pathwidth, and the citation choices look appropriate for the subfield. The technical details appear reproducible from the supplied definitions and proofs. A minor limitation is that the construction is quite specific to this exponential lower bound, so it does not immediately suggest how to push the pathwidth even lower or handle average-case behavior. Within its stated scope, however, the argument is tight and free of obvious gaps. This work is aimed at researchers in parameterized complexity who study the limits of local search on graphs with bounded pathwidth or treewidth. Anyone looking for a concrete example that pathwidth three already suffices to encode hard local-search instances will find the construction directly useful. I would send the paper to peer review; the result is sharp enough and the proofs are supplied, so referees can verify the details without needing additional external evidence.

Referee Report

2 major / 3 minor

Summary. The manuscript constructs a valued constraint satisfaction problem (VCSP) via a controlled doubling procedure whose constraint graph has pathwidth exactly three. From a designated initial assignment, every strict local-search ascent (sequence of improving flips) is shown to have exponential length. The construction improves on earlier examples that required pathwidth at least four and is accompanied by an inductive argument establishing the pathwidth bound together with a potential-function argument establishing the exponential lower bound on ascent length.

Significance. If the construction and its proofs hold, the result demonstrates that pathwidth three already suffices to force exponential-length ascents for strict local search on pseudo-Boolean functions. The explicit construction, the inductive path-decomposition argument, and the potential-function bound constitute concrete, machine-checkable evidence that separates pathwidth-three VCSPs from polynomial-time local search, strengthening the parameterized-complexity picture of local search on sparse graphs.

major comments (2)

[§3] §3, controlled-doubling construction: the inductive step that each doubling preserves a path decomposition of width exactly three must exhibit an explicit elimination ordering or sequence of bags; without it the claim that the final graph has pathwidth three (rather than at most three) is not fully load-bearing for the central separation result.
[§5] §5, potential-function argument: the proof that every improving flip decreases the potential by a multiplicative factor must enumerate all possible improving moves from any reachable assignment, not only the moves that appear in the intended ascent; otherwise the exponential lower bound applies only to a subset of ascents.

minor comments (3)

[Abstract] The abstract and introduction should state the precise exponential base (e.g., 2^{Ω(n)}) and its dependence on the number of variables n.
[Notation] Notation for the valued constraints, the fitness function, and the pathwidth definition should be made uniform between the VCSP section and the pseudo-Boolean section.
[Figure 2] Figure 2 (the small example) would benefit from an explicit listing of the bags in the path decomposition to illustrate the width-three claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation of minor revision. The two major comments identify places where additional explicit detail will strengthen the proofs; we address each below and will incorporate the clarifications in the revised manuscript.

read point-by-point responses

Referee: [§3] §3, controlled-doubling construction: the inductive step that each doubling preserves a path decomposition of width exactly three must exhibit an explicit elimination ordering or sequence of bags; without it the claim that the final graph has pathwidth three (rather than at most three) is not fully load-bearing for the central separation result.

Authors: We agree that an explicit inductive description of the bags is needed to confirm width exactly three. In the revision we will add, in §3, the base-case bags together with the precise rule for updating the bag sequence at each doubling step, showing that every new vertex is introduced in a bag of size four and that the width remains exactly three throughout the construction. revision: yes
Referee: [§5] §5, potential-function argument: the proof that every improving flip decreases the potential by a multiplicative factor must enumerate all possible improving moves from any reachable assignment, not only the moves that appear in the intended ascent; otherwise the exponential lower bound applies only to a subset of ascents.

Authors: The referee correctly notes that the exponential lower bound requires the potential decrease to hold for every improving flip that can occur from any reachable assignment. The controlled-doubling construction restricts the possible flips so severely that a complete case analysis is feasible. We will revise §5 to list all admissible improving moves from reachable states and verify that each reduces the potential by a multiplicative factor of at least 1/2, thereby establishing the bound for every ascent. revision: yes

Circularity Check

0 steps flagged

Explicit construction is self-contained with no circularity

full rationale

The paper's central result is an explicit controlled-doubling construction of a VCSP instance whose constraint graph has pathwidth exactly three (via an explicit path decomposition) while every improving flip sequence from a designated start is exponentially long (via a potential-function argument). Both properties are established directly in the manuscript by the construction itself and its inductive verification; no step reduces a claimed prediction to a fitted parameter, a self-citation chain, or a definitional tautology. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard definitions of pathwidth and VCSPs together with the validity of the newly introduced controlled doubling construction; no numerical free parameters or additional invented entities are indicated.

axioms (1)

domain assumption Pathwidth is an appropriate sparsity measure for bounding the complexity of strict local search on VCSPs
Invoked when the authors argue that pathwidth is the natural parameter for understanding limits on local search power

invented entities (1)

controlled doubling construction no independent evidence
purpose: To produce a VCSP instance of pathwidth three whose fitness landscape forces all ascents to be exponentially long
The main technical contribution introduced to achieve the stated lower bound

pith-pipeline@v0.9.0 · 5520 in / 1260 out tokens · 24195 ms · 2026-05-16T11:47:59.923344+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking matches

?

matches
MATCHES: this paper passage directly uses, restates, or depends on the cited Recognition theorem or module.

Proposition 3. The controlled doubling construction has pathwidth 3. ... K4 minor ... path decomposition of width 3
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_strictMono_of_one_lt echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

T_m = 10(2^m - 1) ... m_k = 2^{k-1}(8n + 16) - 16, s_k = 8(n - k) ... doubling flow ... control flow

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Binary constraints on one additional variable can create exponential ascents
cs.DM 2026-05 unverdicted novelty 7.0

A star gadget with 2n triangles on one central variable in a binary VCSP produces an exponential ascent of length 10*2^n - 9 by intertwining two linear sublandscapes.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper

[1]

Aarts and J

E. Aarts and J. K. Lenstra, eds.Local Search in Combinatorial Optimization. Princeton, NJ, USA: Princeton University Press, 2003

work page 2003
[2]

Arity of polynomials for equivalence classes of pseudo-Boolean functions

T. Batman. “Arity of polynomials for equivalence classes of pseudo-Boolean functions”. Bachelor’s Thesis. Utrecht University, 2025

work page 2025
[3]

On non-serial dynamic programming

U. Bertel` e and F. Brioschi. “On non-serial dynamic programming”. In:Journal of Combi- natorial Theory, Series A14.2 (1973), pp. 137–148.issn: 0097-3165.doi:https://doi. org/10.1016/0097-3165(73)90016-2

work page doi:10.1016/0097-3165(73)90016-2 1973
[4]

Pseudo-boolean optimization

E. Boros and P. L. Hammer. “Pseudo-boolean optimization”. In:Discrete applied mathe- matics123.1-3 (2002), pp. 155–225

work page 2002
[5]

The complexity class Polynomial Local Search (PLS) and PLS-complete problems

M. Borzechowski. “The complexity class Polynomial Local Search (PLS) and PLS-complete problems”. Bachelor’s Thesis. Freie Universitat Berlin, 2016

work page 2016
[6]

The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

C. Carbonnel, M. Romero, and S. ˇZivn´ y. “The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side”. In:SIAM Journal on Computing51.1 (2022), pp. 19–69.doi:10.1137/19M1250121

work page doi:10.1137/19m1250121 2022
[7]

Steepest ascent can be exponential in bounded treewidth problems

D. A. Cohen, M. C. Cooper, A. Kaznatcheev, and M. Wallace. “Steepest ascent can be exponential in bounded treewidth problems”. In:Operations Research Letters48 (3 2020), pp. 217–224

work page 2020
[8]

Cygan, F

M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh.Parameterized algorithms. Springer International Publishing, 2015.doi: 10.1007/978-3-319-21275-3

work page doi:10.1007/978-3-319-21275-3 2015
[9]

On the PLS-complexity of maximum constraint assignment

D. Dumrauf and B. Monien. “On the PLS-complexity of maximum constraint assignment”. In:Theoretical Computer Science469 (2013), pp. 24–52

work page 2013
[10]

Settling the complexity of local max-cut (almost) completely

R. Els¨ asser and T. Tscheuschner. “Settling the complexity of local max-cut (almost) completely”. In:International Colloquium on Automata, Languages, and Programming. Springer. 2011, pp. 171–182

work page 2011
[11]

The worst case behavior of a greedy algorithm for a class of pseudo-boolean functions

M. Emamy-K. “The worst case behavior of a greedy algorithm for a class of pseudo-boolean functions”. In:Discrete Applied Mathematics23.3 (1989), pp. 285–287

work page 1989
[12]

The Random-Facet simplex algorithm on combinatorial cubes

B. G¨ artner. “The Random-Facet simplex algorithm on combinatorial cubes”. In:Random Structures & Algorithms20.3 (2002), pp. 353–381

work page 2002
[13]

Steepest descent can take exponential time for symmetric con- nection networks

A. Haken and M. Luby. “Steepest descent can take exponential time for symmetric con- nection networks”. In:Complex Syst.2.2 (Apr. 1988), pp. 191–196.issn: 0891-2513.url: http://www.complex-systems.com/abstracts/v02%5C_i02%5C_a03.html

work page 1988
[14]

Random-edge is slower than random-facet on abstract cubes

T. D. Hansen and U. Zwick. “Random-edge is slower than random-facet on abstract cubes”. In:Leibniz International Proceedings in Informatics55 (2016), pp. 51–1

work page 2016
[15]

Long path problems

J. Horn, D. E. Goldberg, and K. Deb. “Long path problems”. In:International Conference on Parallel Problem Solving from Nature. Springer. 1994, pp. 149–158

work page 1994
[16]

The simplex algorithm with the pivot rule of maximizing criterion im- provement

R. G. Jeroslow. “The simplex algorithm with the pivot rule of maximizing criterion im- provement”. In:Discrete Mathematics4.4 (1973), pp. 367–377

work page 1973
[17]

How easy is local search?

D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis. “How easy is local search?” In: Journal of Computer and System Sciences37.1 (1988), pp. 79–100.issn: 0022-0000

work page 1988
[18]

Algorithmic Biology of Evolution and Ecology

A. Kaznatcheev. “Algorithmic Biology of Evolution and Ecology”. PhD thesis. University of Oxford, 2020. 17

work page 2020
[19]

Computational complexity as an ultimate constraint on evolution

A. Kaznatcheev. “Computational complexity as an ultimate constraint on evolution”. In: Genetics212.1 (2019), pp. 245–265

work page 2019
[20]

Representing fitness landscapes by val- ued constraints to understand the complexity of local search

A. Kaznatcheev, D. A. Cohen, and P. Jeavons. “Representing fitness landscapes by val- ued constraints to understand the complexity of local search”. In:Journal of Artificial Intelligence Research69 (2020), pp. 1077–1102

work page 2020
[21]

Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four

A. Kaznatcheev and M. van Marle. “Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four”. In:30th International Conference on Principles and Practice of Constraint Programming (CP 2024). 2024, 17:1–17:16

work page 2024
[22]

Yet another algorithm for dense max cut: go greedy

A. Kaznatcheev and S. Vazquez Alferez. “Greed Is Slow on Sparse Graphs of Oriented Valued Constraints”. In:31st International Conference on Principles and Practice of Con- straint Programming (CP 2025). Ed. by M. G. de la Banda. Vol. 340. Leibniz Interna- tional Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz- Zentrum f¨...

work page doi:10.4230/lipics 2025
[23]

Kaznatcheev and S

A. Kaznatcheev and S. Vazquez Alferez.When is local search both effective and efficient? 2026.doi:10 . 48550 / arXiv . 2410 . 02634. arXiv:2410 . 02634 [cs.DS].url:https : //arxiv.org/abs/2410.02634

work page arXiv 2026
[24]

How good is the simplex algorithm

V. Klee and G. J. Minty. “How good is the simplex algorithm”. In:Inequalities3.3 (1972), pp. 159–175

work page 1972
[25]

The unconstrained binary quadratic programming problem: a survey

G. Kochenberger, J.-K. Hao, F. Glover, M. Lewis, Z. L¨ u, H. Wang, and Y. Wang. “The unconstrained binary quadratic programming problem: a survey”. In:Journal of Combi- natorial Optimization28.1 (2014), pp. 58–81

work page 2014
[26]

On Finding and Verifying Locally Optimal Solutions

M. W. Krentel. “On Finding and Verifying Locally Optimal Solutions”. In:SIAM Journal on Computing19.4 (1990), pp. 742–749

work page 1990
[27]

RANDOM EDGE can be exponential on abstract cubes

J. Matousek and T. Szabo. “RANDOM EDGE can be exponential on abstract cubes.” In: Advances in Mathematics204 (1 2006), pp. 262–277

work page 2006
[28]

Michel and A

L. Michel and A. Scott.Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut

work page
[29]

arXiv:2310.19594 [cs.DS].url:https://arxiv.org/abs/2310.19594

work page arXiv
[30]

On the Power of Nodes of Degree Four in the Local Max-Cut Problem

B. Monien and T. Tscheuschner. “On the Power of Nodes of Degree Four in the Local Max-Cut Problem”. In:Algorithms and Complexity. Ed. by T. Calamoneri and J. Diaz. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp. 264–275

work page 2010
[31]

Integer linear programs and local search for max-cut

S. Poljak. “Integer linear programs and local search for max-cut”. In:SIAM Journal on Computing24.4 (1995), pp. 822–839

work page 1995
[32]

Simple local search problems that are hard to solve

A. A. Sch¨ affer and M. Yannakakis. “Simple local search problems that are hard to solve”. In:SIAM Journal on Computing20.1 (1991), pp. 56–87

work page 1991
[33]

Local search algorithms for combinatorial problems: Analysis, Improvements, and New Applications

T. St¨ utzle. “Local search algorithms for combinatorial problems: Analysis, Improvements, and New Applications”. PhD thesis. TU Darmstadt, 1998

work page 1998
[34]

Complexity of Greedy Local Search for Constraint Satisfaction

M. van Marle. “Complexity of Greedy Local Search for Constraint Satisfaction”. Master’s Thesis. Utrecht University, 2025

work page 2025
[35]

The roles of mutation, inbreeding, crossbreeding, and selection in evolution

S. Wright. “The roles of mutation, inbreeding, crossbreeding, and selection in evolution”. In:Proc. of the 6th International Congress on Genetics. 1932, pp. 355–366. 18

work page 1932