betaFeedback

WorksComputer Science

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by Treewidth

Abstract

We consider valued constraint satisfaction problems (VCSPs) with a fixed finite domain DD and a fixed finite constraint language ΓΓ, in the setting where ΓΓ contains all crisp unary constraints (called hard lists) and the remaining cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let cΓc_Γ be the size of the largest set S⊆DS\subseteq D such that ΓΓ can express (using the usual VCSP closure operations) a binary disequality function on elements of SS. Our main result tightly connects the complexity of the problem parameterized by treewidth to this value cΓc_Γ. (1) The problem can be solved in time (cΓ)tw⋅(∣I∣+∣T∣)O(1)(c_Γ)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)} when given an instance II with a tree decomposition T\mathcal{T} of width tw\mathsf{tw} of the primal graph of II. (2) If cΓ≥2c_Γ\geq 2, there is no such algorithm solving the problem in time (cΓ−ε)tw⋅(∣I∣+∣T∣)O(1)(c_Γ- \varepsilon)^{\mathsf{tw}} \cdot (|I| + |\mathcal{T}|)^{O(1)} for any ε>0\varepsilon > 0, unless the Primal Treewidth SETH (and hence CNF-SETH) fails. In particular, this gives a far-reaching generalization of a similar result of Esmer et al. [ESA 2024] on the optimization version of list homomorphism for graphs.

Funding: George Osipov: Supported by the Swedish Research Council (VR) under grant 2024-00274. Paweł Rzążewski: Supported by the National Science Centre grant 2024/54/E/ST6/00094. Stanislav Živný: Supported by UKRI EP/X024431/1.

Introduction

Constraint Satisfaction Problems (CSPs) and their extensions provide a broad framework encompassing many fundamental algorithmic problems. The Valued Constraint Satisfaction Problem (VCSP) extends this framework to optimization problems. Let DD be a finite nonempty domain. A cost function of arity aa is a function f:Da→Q≥0∪{∞}f : D^a \to\mathbb{Q}_{\ge0} \cup\{\infty\}. For a fixed finite domain DD and a finite set Γ\Gamma of cost functions, an instance of VCSP(Γ\Gamma) consists of a finite set VV of variables and a finite family C\mathcal{C} of constraints. Each constraint C∈CC \in\mathcal{C} is a triple (f,S,w)(f,S,w), where f∈Γf \in\Gamma is the cost function, denoted by cost⁡f(C)\operatorname{cost}_f(C), S∈Varity⁡(f)S \in V^{\operatorname{arity}(f)} is a tuple of arity⁡(f)\operatorname{arity}(f) variables, and w∈Q>0w \in\mathbb{Q}_{>0} is a positive rational weight. The goal is to find an assignment of values to variables that minimizes the total weighted cost of all constraints in C\mathcal{C}.

Over the past decades, considerable effort has been devoted to characterizing the sets Γ\Gamma for which VCSP(Γ\Gamma) is polynomial-time solvable. If every f∈Γf \in\Gamma takes values in {0,∞}\{0,\infty\}, that is, if every constraint is crisp, then VCSP(Γ\Gamma) reduces to a decision problem whose goal is to find a feasible assignment. The Feder–Vardi Dichotomy Conjecture [41], proved by Bulatov [10] and Zhuk [Zhu20] independently, states that every such problem is either polynomial-time solvable or NP-hard. For the case where every f∈Γf \in\Gamma is finite-valued, a dichotomy theorem was proved by Thapper and Živný [79]. Finally, the combination of the work by Kozik and Ochremiak [51] and by Kolmogorov, Krokhin, and Rolínek [49] unified these results by establishing a dichotomy for every fixed finite constraint language Γ\Gamma: VCSP(Γ\Gamma) is either polynomial-time solvable or NP-hard. The search for such dichotomy theorems can be viewed as a systematic search for all relevant algorithmic ideas: a dichotomy theorem identifies a collection of algorithmic techniques and shows that, when none of them applies, no further technique can yield a polynomial-time algorithm, unless P = NP.

For each fixed Γ\Gamma, the dichotomy proofs mentioned above either establish tractability or show that the problem is at least as hard as a known NP-hard problem, such as 3-Coloring or Max Cut. This suffices to distinguish polynomial-time solvable cases from NP-hard ones, but does not provide a finer understanding of the complexity of the hard cases. Intuitively, a problem equivalent to 100-Coloring should be considered harder than one equivalent to 3-Coloring: on kk variables, the former has a search space of size 100k100^k, compared with 3k3^k for the latter. This distinction is invisible from the perspective of polynomial-time solvability versus NP-hardness, since 100-Coloring and 3-Coloring are polynomial-time equivalent. However, in some settings, differences of this kind can be established rigorously. One such setting is the parameterized complexity of problems on graphs of bounded treewidth.

Treewidth. Treewidth is a combinatorial graph parameter that plays a central role in graph structure theory, most prominently in the Graph Minors project of Robertson and Seymour (see, e.g., [72, 73, 74]). From an algorithmic perspective, treewidth measures how close a graph is to being a tree, and hence how effectively the bottom-up dynamic programming techniques used for trees can be extended to it. Many applications in parameterized complexity, approximation-scheme design, and other areas rely crucially on the efficient solvability of problems on graphs of bounded treewidth [25, 7, 30 CFK⁺15, 67]. In particular, given a tree decomposition of width tw⁡\operatorname{tw}, several fundamental problems can be solved in time ctw⁡⋅nO(1)c^{\operatorname{tw}} \cdot n^{O(1)} for some constant c>1c > 1 using fairly standard dynamic programming. A natural goal is to determine the smallest possible value of cc for each problem.

A line of research initiated by Lokshtanov, Marx, and Saurabh [63] showed that many known algorithms are optimal in the following sense: a problem can be solved in time ctw⁡⋅nO(1)c^{\operatorname{tw}} \cdot n^{O(1)}, but, assuming the Strong Exponential-Time Hypothesis (SETH) [47, 18], no algorithm runs in time (c−ε)tw⁡⋅nO(1)(c-\varepsilon)^{\operatorname{tw}} \cdot n^{O(1)} for any ε>0\varepsilon> 0. Recent preprints by OpenAI [69] and Claude (Anthropic) [21] report refutations of the Exponential Time Hypothesis (ETH), and hence also refutations of SETH. However, many of the lower bounds developed over the years remain valid under the weaker conjecture CNF-SETH — that is, nn-variable mm-clause SAT with unbounded clause size cannot be solved in time (2−ε)n⋅(n+m)O(1)(2-\varepsilon)^n \cdot(n+m)^{O(1)} for any ε>0\varepsilon> 0 — which has not been refuted as of this writing. Prior work [48, 58, 60] introduced the even weaker Primal Pathwidth Strong Exponential Time Hypothesis (pw-SETH) and Primal Treewidth Strong Exponential Time Hypothesis (tw-SETH), and showed that they also form a source of hardness for these lower bounds and are in some cases actually equivalent to them. Both of these hypotheses follow from CNF-SETH. For some problems, these lower bounds establish the optimality of straightforward dynamic programming, whereas for others, achieving the optimal base cc requires nontrivial algorithmic ideas. For a broad range of tight treewidth and pathwidth bounds, including counting variants, and results on the hypotheses underlying these bounds, see [63 vRBvL⁺18, CNP⁺22, 48, 8 KLP22, 36, 20, 22, 70, 32, 68, 33, 39 FMM⁺25a, FMM⁺25b]. [65, 35, 58, 59, 60]. The primal graph (or Gaifman graph) of a VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) instance has the variables as its vertices, with two vertices adjacent if the corresponding variables occur together in some constraint. Given a VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) instance and a tree decomposition of width tw⁡\operatorname{tw} of its primal graph, standard dynamic programming solves the instance in time ∣D∣tw⁡⋅nO(1)|D|^{\operatorname{tw}} \cdot n^{O(1)}. Is this running time optimal for every Γ\Gamma for which VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) is NP-hard? For some languages Γ\Gamma, simple improvements are possible, for example when two values a,b∈Da,b \in D play exactly the same role in every cost function of Γ\Gamma. This raises the possibility that less obvious algorithmic ideas could lead to further improvements. Ideally, for every finite Γ\Gamma for which VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) is NP-hard, we would like to identify a constant cΓ>1c_\Gamma> 1, give an algorithm running in time cΓtw⁡⋅nO(1)c_\Gamma^{\operatorname{tw}} \cdot n^{O(1)}, and prove a conditional lower bound ruling out running time (cΓ−ε)tw⁡⋅nO(1)(c_\Gamma-\varepsilon)^{\operatorname{tw}} \cdot n^{O(1)} for every ε>0\varepsilon> 0.

An important step toward the CSP and VCSP dichotomies was the resolution of their conservative cases [9, 57]. The term conservative has been used with somewhat different meanings in the CSP and VCSP literature. For the decision problem CSP⁡(Γ)\operatorname{CSP}(\Gamma), conservativity means that, for every subset S⊆DS \subseteq D, a constraint restricting a variable to SS is available. Equivalently, one may consider the list version of the problem, in which every variable vv is equipped with a “hard list” Lv⊆DL_v \subseteq D, and the goal is to find a solution respecting all these lists. In our setting, this means that Γ\Gamma contains every unary {0,∞}\{0,\infty\}-valued cost function. In the VCSP literature, on the other hand, conservativity means that every finite-valued unary cost function is considered to be available. Equivalently, for each a∈Da \in D, the unary cost function that takes value 11 on aa and 00 on D∖{a}D \setminus\{a\} is available. This can be interpreted as allowing a “soft list” for each variable, specifying a cost cv,dc_{v,d} for assigning value dd to variable vv.

Main result. Our main result determines cΓc_\Gamma when Γ\Gamma allows hard lists (that is, contains every unary {0,∞}\{0,\infty\}-valued cost function) and all its other cost functions are finite-valued. We call such a language a finite-valued hard-list language. Let pow⁡(Γ)\operatorname{pow}(\Gamma) be the set of all cost functions that can be obtained from finite weighted sums of constraints from Γ\Gamma by minimizing over auxiliary variables and allowing an additive rational shift. Let cΓc_\Gamma be the size of the largest set S⊆DS \subseteq D such that pow⁡(Γ)\operatorname{pow}(\Gamma) contains the binary disequality function on SS: that is, there is a function g∈pow⁡(Γ)g \in\operatorname{pow}(\Gamma) such that g(x,x)=1g(x,x)=1 for every x∈Sx \in S and g(x,y)=0g(x,y)=0 for every x,y∈Sx,y \in S, x≠yx \ne y. Note that in our context, we can always make gg have infinite or very large value outside SS.

Theorem 1.1. Let DD be a fixed finite domain and Γ\Gamma a fixed finite-valued hard-list language over DD.

(1) There is an algorithm that, given a VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) instance II together with a tree decomposition T\mathcal{T} of its primal graph of width tw⁡\operatorname{tw}, solves II in time

(cΓ)tw⁡⋅(∣I∣+∣T∣)O(1).(c_\Gamma)^{\operatorname{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)}.

(2) If cΓ≥2c_\Gamma\ge2, for every ε>0\varepsilon> 0, there is no algorithm that solves an instance II of VCSP⁡(Γ)\operatorname{VCSP}(\Gamma), given together with a tree decomposition T\mathcal{T} of its primal graph of width tw⁡\operatorname{tw}, in time

(cΓ−ε)tw⁡⋅(∣I∣+∣T∣)O(1),(c_\Gamma-\varepsilon)^{\operatorname{tw}} \cdot(|I|+|\mathcal{T}|)^{O(1)},

unless tw⁡\operatorname{tw}-SETH is false. The same lower bound holds under pw⁡\operatorname{pw}-SETH with treewidth replaced by pathwidth.

As CNF-SETH implies both tw⁡\operatorname{tw}-SETH and pw⁡\operatorname{pw}-SETH, these results are also true under CNF-SETH. An example deferred to Appendix A clarifies a delicate detail in the definition of cΓc_\Gamma and the statement of Theorem 1.1. It is not necessarily true that restricting every relation in Γ\Gamma to the set S⊆DS \subseteq D yields a language ΓS\Gamma_S with the same complexity: in fact, there is a language Γ\Gamma such that even though VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) requires ∣S∣tw⁡⋅nO(1)|S|^{\operatorname{tw}} \cdot n^{O(1)} time for some S⊆DS \subseteq D, for each S′⊆DS' \subseteq D the problem obtained by restricting Γ\Gamma to S′S' is even polynomial-time solvable. It is possible that in order to express the disequality function on SS appearing in pow⁡(Γ)\operatorname{pow}(\Gamma), we need to rely on values outside SS. For example, it is possible that the optimum running time is 2tw⁡⋅nO(1)2^{\operatorname{tw}} \cdot n^{O(1)}, but restricting the domain to every subset of size two gives a polynomial-time solvable problem.

The lower bound of Theorem 1.1(2) follows fairly easily from the way cΓc_\Gamma is formulated. A binary disequality function over a domain S⊆DS \subseteq D of size ∣S∣≥3|S| \ge3 can be used to express ∣S∣|S|-COLORING: replacing each edge with such a constraint, the optimum value is 00 if and only if the graph has an ∣S∣|S|-coloring. It has been established in earlier work [58, 60] that qq-COLORING for q≥3q \ge3 has no (q−ε)tw⁡⋅nO(1)(q-\varepsilon)^{\operatorname{tw}} \cdot n^{O(1)} time algorithm for any ε>0\varepsilon> 0 (assuming tw⁡\operatorname{tw}-SETH, similarly for pathwidth under pw⁡\operatorname{pw}-SETH). For ∣S∣=2|S|=2, we can use a similar reduction from MAX CUT, for which lower bounds are also known [60, 58, 48, 35]. Therefore, the majority of the proof is devoted to the upper bound of Theorem 1.1(1): showing that there are algorithmic ideas that allow us to reduce the running time precisely to (cΓ)tw⋅nO(1)(c_{\Gamma})^{\mathrm{tw}} \cdot n^{O(1)}. That is, we need to make a connection between cΓc_{\Gamma}, which was defined by existence of cost functions in pow⁡(Γ)\operatorname{pow}(\Gamma), and the existence of algorithmically exploitable structural properties of VCSP⁡(Γ)\operatorname{VCSP}(\Gamma).

Soft lists. Let Γ\Gamma be a finite-valued language that allows all soft lists (that is, contains every unary {0,1}\{0,1\}-valued cost function that takes value 1 on exactly one element of DD). We call such a language a finite-valued soft-list language. Let Γ′\Gamma' be the extension of Γ\Gamma to a finite-valued hard-list language by introducing every {0,∞}\{0,\infty\}-valued unary cost function. It is easy to see that VCSP⁡(Γ)\operatorname{VCSP}(\Gamma) and VCSP⁡(Γ′)\operatorname{VCSP}(\Gamma') have essentially the same complexity: hard lists can be simulated by imposing sufficiently large finite penalties on excluded values. Thus, applying Theorem 1.1 to Γ′\Gamma' yields a precise complexity characterization for every finite-valued soft-list language Γ\Gamma. In particular, our result refines the polynomial-time versus NP-hard dichotomy of Kolmogorov and Živný [57] for finite-valued conservative VCSP by determining the optimal base of the exponent in the NP-hard cases. We can therefore distinguish between the complexities of different NP-hard cases of VCSP⁡(Γ)\operatorname{VCSP}(\Gamma).

As we shall see, both the optimal algorithm and the value of cΓc_{\Gamma} are significantly easier to describe for finite-valued soft-list languages: in the NP-hard cases, cΓc_{\Gamma} is exactly the number of equivalence classes under a relation called additive equivalence. Accordingly, we organize the proof by first establishing the result for finite-valued soft-list languages and then building on it to prove Theorem 1.1 for finite-valued hard-list languages. Much of the technical difficulty in the hard-list setting lies in expressing all soft lists on a certain subset of the domain DD.

Comparison with graph homomorphisms. A special case of Theorem 1.1 was established by Esmer et al. [35] in their study of the Edge-Deletion List Homomorphism problem.1 In our terminology, this corresponds to the case where, apart from the hard-list functions, Γ\Gamma contains only a single finite-valued cost function, which is binary, symmetric, and {0,1}\{0,1\}-valued. Even in this restricted setting, obtaining the optimal base of the exponent requires several nontrivial algorithmic ideas:

  • Polynomial-time solvability via maximum flows. A complete characterization must account for the polynomial-time solvable cases. These cases turn out to be reducible to maximum flow computations.

References

  1. [1]Amir Abboud and Kevin Lewi. Exact weight subgraphs and the $k$-Sum conjecture. In Fedor V. Fomin, Rusins Freivalds, Marta Z. Kwiatkowska, and David Peleg, editors, Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, volume 7965 of Lecture Notes in Computer Science, pages 1–12. Springer, 2013. doi:10.1007/978-3-642-39206-1_1.DOI
  2. [2]Josh Alman and Virginia Vassilevska Williams. Truly subquadratic 3SUM and truly subcubic APSP via triangles in sparse lopsided graphs, 2026. arXiv:2610.06783.arxiv.org/abs/2610.06783
  3. [3]Lucas Bordeaux, Marco Cadoli, and Toni Mancini. A unifying framework for structural properties of CSPs: Definitions, complexity, tractability. J. Artif. Intell. Res., 32:607–629, 2008. doi:10.1613/JAIR.2538.DOI
  4. [4]Stefano Bistarelli, Boi Faltings, and Nicoleta Neagu. Interchangeability in soft CSPs. In Barry O’Sullivan, editor, Recent Advances in Constraints, Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, Cork, Ireland, June 19-21, 2002. Selected Papers, volume 2627 of Lecture Notes in Computer Science, pages 31–46. Springer, 2002. doi:10.1007/3-540-36607-5_3.DOI
  5. [5]Fahiem Bacchus and Adam J. Grove. Graphical models for preference and utility. In Philippe Besnard and Steve Hanks, editors, UAI ’95: Proceedings of the Eleventh Annual Conference on Uncertainty in Artificial Intelligence, Montreal, Quebec, Canada, August 18-20, 1995, pages 3–10. Morgan Kaufmann, 1995. URL: https://dl.acm.org/doi/10.5555/2074158.2074159.
  6. [6]Endre Boros and Peter L. Hammer. Pseudo-Boolean optimization. Discret. Appl. Math., 123(1–3):155–225, 2002. doi:10.1016/S0166-218X(01)00341-9.DOI
  7. [7]Hans L. Bodlaender and Arie M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. Comput. J., 51(3):255–269, 2008. doi:10.1093/COMJNL/BXM037.DOI
  8. [8]Glencora Borradaile and Hung Le. Optimal dynamic program for r-domination problems over tree decompositions. In Jiong Guo and Danny Hermelin, editors, 11th International Symposium on Parameterized and Exact Computation, IPEC 2016, Aarhus, Denmark, August 24-26, 2016, volume 63 of LIPIcs, pages 8:1–8:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPIcs.IPEC.2016.8.DOI
  9. [9]Andrei A. Bulatov. Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log., 12(4):24:1–24:66, 2011. doi:10.1145/1970398.1970400.DOI
  10. [10]Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319–330. IEEE Computer Society, 2017. doi:10.1109/FOCS.2017.37.DOI
  11. [11]David A. Cohen, Martin C. Cooper, Páidí Creed, Peter G. Jeavons, and Stanislav Živný. An algebraic theory of complexity for discrete optimization. SIAM J. Comput., 42(5):1915–1939, 2013. doi:10.1137/130906398.DOI
  12. [13]David A. Cohen, Martin C. Cooper, Peter Jeavons, and Andrei A. Krokhin. The complexity of soft constraint satisfaction. Artif. Intell., 170(11):983–1016, 2006. doi:10.1016/J.ARTINT.2006.04.002.DOI
  13. [14]Martin C. Cooper, Simon de Givry, Martí Sánchez-Fibla, Thomas Schiex, Matthias Zytnicki, and Tomáš Werner. Soft arc consistency revisited. Artif. Intell., 174(7-8):449–478, 2010. doi:10.1016/J.ARTINT.2010.02.001.DOI
  14. [15]Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1–41:24, 2016. doi:10.1145/2925416.DOI
  15. [16]Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. doi:10.1007/978-3-319-21275-3.DOI
  16. [17]Timothy M. Chan, Reina Itakura, Zhiyuan Ma, and Yuancheng Yu. 3SUM made simpler (without matrix multiplication), k-SUM hypothesis refuted for odd k, and real 3SUM/APSP derandomized, 2026. arXiv:2610.42012.
  17. [18]Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability of small depth circuits. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 75–85. Springer, 2009. doi:10.1007/978-3-642-11269-0_6.DOI
  18. [19]David A. Cohen, Peter G. Jeavons, and Stanislav Živný. The expressive power of valued constraints: Hierarchies and collapses. Theor. Comput. Sci., 409(1):137–153, 2008. doi:10.1016/J.TCS.2008.08.036.DOI
  19. [20]Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast Hamiltonicity checking via bases of perfect matchings. J. ACM, 65(3):12:1–12:46, 2018. doi:10.1145/3148227.DOI
  20. [21]Claude (Anthropic). A 2^{o(n)} time algorithm for 3-SAT. Anthropic formal-math preprint, October 2026. URL: https://github.com/anthropics/formal-math/blob/main/eth/paper.pdf.
  21. [22]Radu Curticapean, Nathan Lindzey, and Jesper Nederlof. A tight lower bound for counting Hamiltonian cycles via matrix rank. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1080–1099. SIAM, 2018. doi:10.1137/1.9781611975031.70.
  22. [24]Martin C. Cooper. Reduction operations in fuzzy or valued constraint satisfaction. Fuzzy Sets Syst., 134(3):311–342, 2003. doi:10.1016/S0165-0114(02)00134-3.DOI
  23. [25]Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput., 85(1):12–75, 1990. doi:10.1016/0890-5401(90)90043-H.DOI
  24. [26]Clément Carbonnel, Miguel Romero, and Stanislav Živný. The complexity of general-valued constraint satisfaction problems seen from the other side. SIAM J. Comput., 51(1):19–69, 2022. doi:10.1137/19M1250121.DOI
  25. [27]Johan Desmet, Marc De Maeyer, Bart Hazes, and Ignace Lasters. The dead-end elimination theorem and its use in protein side-chain positioning. Nature, 356(6369):539–542, 1992. doi:10.1038/356539a0.DOI
  26. [28]Johan Desmet, Marc De Maeyer, and Ignace Lasters. Theoretical and algorithmical optimization of the dead-end elimination theorem. In Pacific Symposium on Biocomputing, pages 122–133, 1997. doi:10.1142/3353.
  27. [29]Simon de Givry, Steven D. Prestwich, and Barry O’Sullivan. Dead-end elimination for weighted CSP. In Christian Schulte, editor, Principles and Practice of Constraint Programming - 19th International Conference, CP 2013, Uppsala, Sweden, September 16-20, 2013. Proceedings, volume 8124 of Lecture Notes in Computer Science, pages 263–272. Springer, 2013. doi:10.1007/978-3-642-40627-0_22.DOI
  28. [30]Erik D. Demaine and MohammadTaghi Hajiaghayi. The bidimensionality theory and its algorithmic applications. Comput. J., 51(3):292–302, 2008. doi:10.1093/COMJNL/BXM033.DOI
  29. [31]Martin Dvorak and Vladimir Kolmogorov. Generalized minimum 0-extension problem and discrete convexity. Math. Program., 209(1–2):279–322, 2025. doi:10.1007/S10107-024-02064-5.DOI
  30. [32]Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. New algorithms for mixed dominating set. Discret. Math. Theor. Comput. Sci., 23(1), 2021. doi:10.46298/DMTCS.6824.DOI
  31. [33]Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. Upper dominating set: Tight algorithms for pathwidth and sub-exponential approximation. Theor. Comput. Sci., 923:271–291, 2022. doi:10.1016/j.tcs.2022.05.013.DOI
  32. [34]Mina Dalirrooyfard, Andrea Lincoln, Barna Saha, and Virginia Vassilevska Williams. Average-case hardness of parity problems: Orthogonal vectors, k-SUM and more. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4613–4643. SIAM, 2025. doi:10.1137/1.9781611978322.158.DOI
  33. [35]Barış Can Esmer, Jacob Focke, Dániel Marx, and Paweł Rzążewski. List homomorphisms by deleting edges and vertices: Tight complexity bounds for bounded-treewidth graphs. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors, 32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, volume 308 of LIPIcs, pages 39:1–39:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ESA.2024.39.
  34. [36]László Egri, Dániel Marx, and Paweł Rzążewski. Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization. In Rolf Niedermeier and Brigitte Vallée, editors, 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, Caen, France, February 28 – March 3, 2018, volume 96 of LIPIcs, pages 27:1–27:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. doi:10.4230/LIPIcs.STACS.2018.27.DOI
  35. [39]Jacob Focke, Dániel Marx, and Paweł Rzążewski. Counting list homomorphisms from graphs of bounded treewidth: Tight complexity bounds. ACM Trans. Algorithms, 20(2):11:1–11:32, 2024. doi:10.1145/3640814.DOI
  36. [40]Eugene C. Freuder. Complexity of k-tree structured constraint satisfaction problems. In Howard E. Shrobe, Thomas G. Dietterich, and William R. Swartout, editors, Proceedings of the 8th National Conference on Artificial Intelligence. Boston, Massachusetts, USA, July 29 - August 3, 1990, 2 Volumes, pages 4–9. AAAI Press / The MIT Press, 1990. URL: http://www.aaai.org/Library/AAAI/1990/aaai90-001.php.
  37. [41]Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput., 28(1):57–104, 1998. doi:10.1137/S0097539794266766.DOI
  38. [42]Peter Fulla and Stanislav Živný. On planar valued CSPs. J. Comput. Syst. Sci., 87:104–118, 2017. doi:10.1016/J.JCSS.2017.03.005.DOI
  39. [43]M. R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theor. Comput. Sci., 1(3):237–267, 1976. doi:10.1016/0304-3975(76)90059-1.DOI
  40. [44]R. F. Goldstein. Efficient rotamer elimination applied to protein side-chains and related spin glasses. Biophysical Journal, 66(5):1335–1340, 1994. doi:10.1016/S0006-3495(94)80923-3.DOI
  41. [45]Anna Huber, Andrei A. Krokhin, and Robert Powell. Skew bisubmodularity and valued CSPs. SIAM J. Comput., 43(3):1064–1084, 2014. doi:10.1137/120893549.DOI
  42. [46]Maher Helaoui and Wady Naanaa. Modularity-based decompositions for valued CSP. Ann. Math. Artif. Intell., 67(2):165–187, 2013. doi:10.1007/S10472-013-9351-0.DOI
  43. [47]Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367–375, 2001. doi:10.1006/JCSS.2000.1727.DOI
  44. [48]Yoichi Iwata and Yuichi Yoshida. On the equivalence among problems of bounded width. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, volume 9294 of Lecture Notes in Computer Science, pages 754–765. Springer, 2015. doi:10.1007/978-3-662-48350-3_63.DOI
  45. [49]Vladimir Kolmogorov, Andrei A. Krokhin, and Michal Rolínek. The complexity of general-valued CSPs. SIAM J. Comput., 46(3):1087–1110, 2017. doi:10.1137/16M1091836.
  46. [51]Marcin Kozik and Joanna Ochremiak. Algebraic properties of valued constraint satisfaction problem. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 846–858. Springer, 2015. doi:10.1007/978-3-662-47672-7_69.DOI
  47. [52]Gábor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, and Yuan Zhou. Linear programming, width-1 CSPs, and robust satisfaction. In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, pages 484–495. ACM, 2012. doi:10.1145/2090236.2090274.DOI
  48. [53]Frances Y. Kuo, Ian H. Sloan, Grzegorz W. Wasilkowski, and Henryk Woźniakowski. On decompositions of multivariate functions. Math. Comput., 79(270):953–966, 2010. doi:10.1090/S0025-5718-09-02319-9.DOI
  49. [54]Vladimir Kolmogorov, Johan Thapper, and Stanislav Živný. The power of linear programming for general-valued CSPs. SIAM J. Comput., 44(1):1–36, 2015. doi:10.1137/130945648.DOI
  50. [55]Arie M. C. A. Koster, Stan P. M. van Hoesel, and Antoon W. J. Kolen. Solving frequency assignment problems via tree-decomposition. Research Memorandum 99/011, METEOR, Maastricht University, 1999. doi:10.26481/umamet.1999011.DOI
  51. [56]Arie M. C. A. Koster, Stan P. M. van Hoesel, and Antoon W. J. Kolen. Solving partial constraint satisfaction problems with tree decomposition. Networks, 40(3):170–180, 2002. doi:10.1002/NET.10046.DOI
  52. [57]Vladimir Kolmogorov and Stanislav Živný. The complexity of conservative valued CSPs. J. ACM, 60(2):10:1–10:38, 2013. doi:10.1145/2450142.2450146.DOI
  53. [58]Michael Lampis. The primal pathwidth SETH. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 1494–1564. SIAM, 2025. doi:10.1137/1.9781611978322.47.DOI
  54. [59]Michael Lampis. Circuits and backdoors: Five shades of the SETH. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1945–2001. SIAM, 2026. doi:10.1137/1.9781611978971.71.DOI
  55. [60]Michael Lampis. k-SUM hardness implies treewidth-SETH. In Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1916–1944. SIAM, 2026. doi:10.1137/1.9781611978971.70.DOI
  56. [61]Michael Lampis. k-SUM hardness implies treewidth-SETH, 2026. arXiv:2510.08185v3.arxiv.org/abs/2510.08185
  57. [62]Ignace Lasters, Marc De Maeyer, and Johan Desmet. Enhanced dead-end elimination in the search for the global minimum energy conformation of a collection of protein side chains. Protein Engineering, 8(8):815–822, 1995. doi:10.1093/protein/8.8.815.DOI
  58. [63]Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Known algorithms on graphs of bounded treewidth are probably optimal. ACM Trans. Algorithms, 14(2):13:1–13:30, 2018. doi:10.1145/3170442.DOI
  59. [64]Christophe Lecoutre, Olivier Roussel, and Djamel E. Dehani. WCSP integration of soft neighborhood substitutability. In Michela Milano, editor, Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Québec City, QC, Canada, October 8-12, 2012. Proceedings, volume 7514 of Lecture Notes in Computer Science, pages 406–421. Springer, 2012. doi:10.1007/978–3–642–33558–7_31.
  60. [65]Michael Lampis and Manolis Vasilakis. Structural parameterizations for two bounded degree problems revisited. ACM Trans. Comput. Theory, 16(3):17:1–17:51, 2024. doi:10.1145/3665156.DOI
  61. [66]Chavalit Likitvivatanavong and Roland H. C. Yap. Eliminating redundancy in CSPs through merging and subsumption of domain values. SIGAPP Appl. Comput. Rev., 13(2):20–29, 2013. doi:10.1145/2505420.2505422.DOI
  62. [67]Dániel Marx. Four shorts stories on surprising algorithmic uses of treewidth. In Fedor V. Fomin, Stefan Kratsch, and Erik Jan van Leeuwen, editors, Treewidth, Kernels, and Algorithms - Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, volume 12160 of Lecture Notes in Computer Science, pages 129–144. Springer, 2020. doi:10.1007/978–3–030–42071–0_10.DOI
  63. [68]Dániel Marx, Govind S. Sankar, and Philipp Schepper. Degrees and gaps: Tight complexity results of general factor problems parameterized by treewidth and cutwidth. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021, volume 198 of LIPIcs, pages 95:1–95:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.95.DOI
  64. [69]OpenAI. The exponential time hypothesis is false. OpenAI Math Release preprint, October 2026. Dated October 25, 2026. URL: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.
  65. [70]Karolina Okrasa, Marta Piecyk, and Paweł Rzążewski. Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, Pisa, Italy (Virtual Conference), September 7-9, 2020, volume 173 of LIPIcs, pages 74:1–74:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPI CS.ESA.2020.74.arxiv.org/abs/2006.11155
  66. [71]N. A. Pierce, J. A. Spriet, J. Desmet, and S. L. Mayo. Conformational splitting: A more powerful criterion for dead-end elimination. Journal of Computational Chemistry, 21(11):999–1009, 2000. doi:10.1002/1096-987X(200008)21:11<999::AID-JCC9>3.0.CO;2–A.
  67. [72]Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986. doi:10.1016/0196-6774(86)90023-4.DOI
  68. [73]Neil Robertson and Paul D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory B, 41(1):92–114, 1986. doi:10.1016/0095-8956(86)90030-4.DOI
  69. [74]Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory B, 63(1):65–110, 1995. doi:10.1006/JCTB.1995.1006.DOI
  70. [75]Alexander Shekhovtsov. Higher order maximum persistency and comparison theorems. Comput. Vis. Image Underst., 143:54–79, 2016. doi:10.1016/J.CVIU.2015.05.002.DOI
  71. [76]Rustem Takhanov. A dichotomy theorem for the general minimum cost homomorphism problem. In Jean-Yves Marion and Thomas Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, March 4-6, 2010, volume 5 of LIPIcs, pages 657–668. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. doi:10.4230/LIPICS.STACS.2010.2493.DOI
  72. [77]Cyril Terrioux and Philippe Jégou. Bounded backtracking for the valued constraint satisfaction problems. In Francesca Rossi, editor, Principles and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, September 29 – October 3, 2003, Proceedings, volume 2833 of Lecture Notes in Computer Science, pages 709–723. Springer, 2003. doi:10.1007/978-3-540-45193-8_48.DOI
  73. [78]Donald M. Topkis. Supermodularity and Complementarity. Princeton University Press, 1998. doi:10.1515/9781400822539.
  74. [79]Johan Thapper and Stanislav Živný. The complexity of finite-valued CSPs. J. ACM, 63(4):37:1–37:33, 2016. doi:10.1145/2974019.DOI
  75. [81]Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians, (ICM 2018), volume 4, pages 3447–3487. World Scientific, 2018. doi:10.1142/9789813272880_0188.DOI

Paper details

vlnc:W_48vjz7d3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 2

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-5.6 Sol (bare), GPT-6 Astra, GPT-6.1 Sol, various large language models

View statement
Looking for related papers…
Contents