Pith. sign in

REVIEW 6 minor 37 references

Pure Nash Equilibria in Graphical Games of Bounded Width Revisited

T0 review · 0 major / 6 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read PNE in Graphical Games: Better Algorithms, Corrected Hardness

desk verdict Corrects a standing error in the literature, gives improved algorithms with matching lower bounds, and proves a tight combinatorial bound on graph square widths. The W[1]-hardness result disproving Thomas-van Leeuwen is clean and important. read the letter →

arxiv 2607.07627 v1 pith:ZYWV7VMJ submitted 2026-07-08 cs.DS cs.CCcs.GT

Michael Lampis , Yiren Lu This is my paper · ORCID
classification cs.DScs.CCcs.GT
keywords textalphaalgorithmdeltawidthdependencegraphinput
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper revisits the complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE), parameterized by graph width measures (treewidth, pathwidth, cutwidth) and maximum degree Δ. The authors make three main contributions. First, they identify a flaw in a prior algorithm that claimed to remove the exponential dependence on Δ from the treewidth-based running time; they prove the problem is W[1]-hard parameterized by treewidth, so no such algorithm can exist unless FPT = W[1]. Second, they improve the natural dynamic programming dependence from α^((Δ+1)·tw) to α^(⌊2Δ/3+1⌋·tw), α^(⌊Δ/2+1⌋·pw), and α^(ctw), by tightening a combinatorial bound relating the width of a graph G, its maximum degree, and the width of its square G² (or co-neighbor graph G_co). Third, they show the pathwidth and cutwidth algorithms are likely optimal: improving them is equivalent to falsifying the pw-SETH, a standard fine-grained complexity hypothesis. The central technical object is the co-neighbor graph G_co of the game graph, whose width controls the CSP encoding's complexity; the key mechanism is a refined decomposition that avoids adding all out-neighbors of every vertex to every bag, instead tracking only a minority subset and inserting bags at transition points.

What carries the argument

The co-neighbor graph G_co of the game digraph, whose width determines CSP-solving cost; a refined tree/path decomposition of G_co that tracks 'present' vs 'future' out-neighbors of each vertex and inserts bags at the transition ('switching leaf' for treewidth, 'becoming heavy' for pathwidth), saving a constant fraction of neighbors per bag.

What would settle it

If the pw-SETH is false (i.e., SAT parameterized by pathwidth can be solved in (2−ε)^pw time), then the optimality of the pathwidth and cutwidth PNE algorithms collapses, and the equivalence in Theorem 2 becomes vacuous.

Watch

Extended reading notes

Core claim

The standard bound tw(G²) ≤ (Δ+1)·tw(G) is not tight. By carefully splitting each vertex's out-neighborhood into present and future portions and inserting bags at the transition point where a vertex becomes 'heavy', one can achieve tw(G_co) ≤ ⌊2Δ/3+1⌋·tw(G) and pw(G_co) ≤ ⌊Δ/2+1⌋·pw(G), yielding constant-factor improvements in the exponent of PNE algorithms. These bounds are shown to be tight for both pathwidth and treewidth via explicit graph families, and the resulting algorithms for pathwidth and cutwidth are optimal under the pw-SETH. Simultaneously, the problem is W[1]-hard parameterized by treewidth (even vertex cover) when α = 2, refuting a prior claimed FPT algorithm.

Load-bearing premise

The optimality claims for the pathwidth and cutwidth algorithms rely on the pw-SETH, which asserts that the standard dynamic programming algorithm for SAT parameterized by pathwidth cannot be improved from 2^pw to (2−ε)^pw. This is an unproven complexity hypothesis stronger than P ≠ NP; if it fails, the claimed lower bounds collapse.

Editorial extensions

If this is right

  • Any algorithm for PNE in graphical games parameterized by treewidth with running time α^(f(Δ)·tw) must have f(Δ) = Ω(Δ) unless W[1] = FPT, settling the parameterized complexity landscape for this problem.
  • The tightened width bounds on graph squares (Corollary 4) apply to any problem whose complexity depends on tw(G²) or pw(G²), potentially improving algorithms for graph coloring, distance labeling, and related problems beyond game theory.
  • The gap between the treewidth constant (2Δ/3) and pathwidth constant (Δ/2) is unusual—most graph problems have identical complexity for these two parameters—suggesting PNE computation may be a natural problem that genuinely distinguishes treewidth from pathwidth.
  • The equivalence between improving the PNE algorithms and falsifying the pw-SETH means this problem serves as a complete problem for the pw-SETH at these parameter regimes, making it a useful reduction target for future lower bounds.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. This paper revisits the parameterized complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE). It makes three contributions: (1) showing that a prior algorithm by Thomas and van Leeuwen [Algorithmica 2015] claiming α^{O(tw)} dependence is flawed, by proving W[1]-hardness parameterized by vertex cover (Theorem 8); (2) improving the natural DP algorithm's parameter dependence from α^{(Δ+1)·tw} to α^{⌊2Δ/3+1⌋·tw}, α^{⌊Δ/2+1⌋·pw}, and α^{ctw} (Theorem 1), via tightened combinatorial bounds on the width of the co-neighbor graph G_co (Theorems 10–13); and (3) showing that the pathwidth and cutwidth algorithms are optimal under the pw-SETH, in the sense that improving them is equivalent to falsifying that hypothesis (Theorem 2, Theorems 23–24).

Significance. The paper makes a valuable contribution on multiple fronts. The correction of the Thomas–van Leeuwen result is important for the field, as the flawed algorithm appears to have been accepted as state of the art. The tightened bounds on tw(G²) and pw(G²) in terms of Δ and the original graph's width (Corollary 4) are of independent combinatorial interest and could find further applications. The conditional lower bounds are notably tight: the paper establishes equivalence (not just implication) with the pw-SETH, which is a clean and strong result. The tightness examples (Theorems 16–17) with the bramble-based lower bound on H_n (Theorem 18, Propositions 21–22) provide concrete evidence that the combinatorial bounds cannot be improved further. The gap between the treewidth and pathwidth constants (2/3 vs. 1/2) is an intriguing open question that the paper honestly flags.

minor comments (6)
  1. §4.1, Theorem 10: The notation N^⪯_i(v) and N^≻_i(v) is introduced inline but could benefit from a formal definition box or a clearer initial statement, as these objects are used heavily in both Theorems 10 and 11.
  2. §4.1, Theorem 11: The concept of 'switching leaf' is central to the treewidth construction but is defined somewhat tersely. A brief paragraph explaining the intuition for why a unique leaf of T[v|heavy] can always be selected, and how the switching path interacts with the join node construction, would improve readability.
  3. Appendix A: The counterexample to [35] is clear and convincing. It might be worth cross-referencing this example in Section 3 (where Theorem 8 is stated) so readers are aware that a concrete counterexample exists in the appendix.
  4. §5, Theorem 23: The reduction achieves Δ = 2k−1 (odd). The paper notes in §6 that tightening the lower bound for even Δ is open. It would be helpful to briefly state in Theorem 23 itself that the result applies only to odd Δ, for precision.
  5. §4.3, Theorem 16: The pathwidth lower bound argument relies on G²_{k,p} containing an n×n grid as a subgraph. The justification is given in two sentences; a slightly more detailed explanation of why the pivot vertex connections guarantee the grid minor/subgraph would strengthen the proof.
  6. References: [27] (Lampis, SODA 2025) and [28] (Lampis, SODA 2026) are both by one of the authors. This is appropriately disclosed through standard citation, but the authors may wish to explicitly note that the pw-SETH was introduced by one of them in §1 (Other related work) for full transparency.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and the positive assessment. The referee's summary accurately captures the three main contributions of the paper: (1) the identification of the flaw in the Thomas–van Leeuwen algorithm and the W[1]-hardness result, (2) the improved combinatorial bounds on the width of the co-neighbor graph yielding improved algorithms, and (3) the tight conditional lower bounds under the pw-SETH. The referee raised no major comments requiring revision. We are grateful for the referee's acknowledgment of the independent interest of the combinatorial bounds (Corollary 4), the strength of the equivalence results (Theorem 2), and the tightness examples (Theorems 16–18). We note the referee's interest in the gap between the treewidth and pathwidth constants (2/3 vs. 1/2), which we have flagged as an open question in Section 6. We remain open to any minor editorial suggestions the referee may have.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity found; derivation chain is self-contained

full rationale

The paper's three contributions are each independently grounded. (1) The W[1]-hardness reduction (Theorem 8) is a self-contained reduction from Multicolored Clique with explicit payoff matrices and vertex cover argument. (2) The improved algorithms (Theorem 1) follow from a clean chain: graphical game → CSP (Theorem 14, constructive) → standard CSP algorithm on G_co (Theorem 15, cited from [13]) → constructive upper bounds on width of G_co (Theorems 10–13, each with explicit decomposition constructions and full validity proofs in appendices). The tightness examples (Theorems 16–17) use bramble-based lower bounds (Theorem 18, Propositions 21–22) that are self-contained. (3) The conditional lower bounds (Theorems 23–24) give explicit, self-contained reductions from CSP to PNE showing that improving the PNE algorithms would falsify the pw-SETH. The pw-SETH itself is cited from [27] (Lampis, SODA 2025), where one author overlaps, but it is a complexity conjecture used by multiple independent research groups ([11, 15, 19, 29, 32]) and is treated as a hypothesis, not as a proven theorem. The reverse direction of Theorem 2 uses [27, Theorem 3.2] (CSP improvement from pw-SETH falsification) combined with the paper's own Theorem 14, which is a legitimate use of an externally published result. No step in any derivation chain reduces to its own inputs by construction, and no 'prediction' is a renamed fit. The single self-citation to [27] is minor and not load-bearing in a circular sense — the paper's own explicit reductions are the substantive content. Score 1 reflects this minor self-citation with no circularity in the central claims.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The paper introduces no free parameters (it is a purely theoretical work with no fitted constants). The axioms are standard complexity hypotheses (pw-SETH, W[1]≠FPT) and established mathematical results (CSP algorithms, bramble duality). The invented entities (co-neighbor graph, tightness examples) are combinatorial constructions with verifiable properties, not postulated physical objects.

assumptions (4)
  • domain assumption pw-SETH: the standard DP for SAT parameterized by pathwidth cannot be improved from 2^pw to (2-ε)^pw
    Invoked in Theorem 2 and Section 5 to establish lower bounds. Introduced by Lampis [27]. Not a proven theorem but a standard complexity hypothesis used by multiple independent groups.
  • domain assumption W[1] ≠ FPT
    Invoked in Section 3 to show that the algorithm of [35] would imply FPT=W[1], which is considered unlikely under standard complexity-theoretic assumptions.
  • standard math Standard CSP algorithm: CSP on treewidth tw with alphabet size |Σ| can be solved in time |Σ|^(tw+1) · n^O(1)
    Theorem 15, cited from [13]. Used as the algorithmic backbone for the PNE algorithms after reducing to CSP on the co-neighbor graph.
  • standard math Bramble duality: G has a bramble of order ≥ k iff tw(G) ≥ k-1
    Theorem 20, cited from [34]. Used to prove the treewidth lower bound for the tightness example H_n (Theorem 18).
invented entities (2)
  • Co-neighbor graph G_co independent evidence
    purpose: Generalization of the square graph to digraphs; the primal graph of the CSP encoding of PNE
    Definition 5. A natural graph-theoretic object; the paper proves tight bounds on its width (Theorem 3) and uses it for both algorithms and lower bounds. Not a new physical entity but a definitional tool.
  • Graph family G_{k,p} and H_n independent evidence
    purpose: Tightness examples showing the combinatorial bounds of Theorem 3 and Corollary 4 cannot be improved
    Constructions in Theorems 16-17. Explicit graph families with verifiable width properties. H_n = T_n □ P_n is a novel combinatorial object whose treewidth is bounded via a bramble argument.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pure Nash Equilibria in Graphical Games of Bounded Width Revisited." pith.science (2026). https://pith.science/paper/ZYWV7VMJ

@misc{pith2026260707627,
  author       = {Pith},
  title        = {Pith review of: Pure Nash Equilibria in Graphical Games of Bounded Width Revisited},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZYWV7VMJ}},
  note         = {Machine review of arXiv:2607.07627}
}
abstract

We revisit the complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE) parameterized by standard measures of the input graph, such as treewidth. The natural dynamic programming algorithm for this problem has parameter dependence $\alpha^{(\Delta+1)\text{tw}}$ where $\alpha$ is the maximum number of strategies available to each player, each player's utility depends on at most $\Delta$ other players, and the input graph has width $\text{tw}$. Our first contribution is to point out that an algorithm by Thomas and van Leeuwen [Algorithmica 2015] claiming to improve this dependence to $\alpha^{O(\text{tw})}$ is flawed and, more strongly, such an algorithm would imply that FPT=W[1]. We then set out to pinpoint the fine-grained complexity of this problem with respect to standard parameters and show that the natural DP algorithm is not optimal, as the problem can be solved with dependence $\alpha^{\lfloor \frac{2\Delta}{3} + 1 \rfloor \text{tw}}$, $\alpha^{\lfloor \frac{\Delta}{2} + 1 \rfloor \text{pw}}$, and $\alpha^{\text{ctw}}$, where $\text{pw}, \text{ctw}$ are the pathwidth and cutwidth of the input respectively. Our main algorithmic tool is a tightening of the relationship between the width of a graph $G$, its maximum degree, and the width of $G^2$, which may be of independent interest. Complementing these results, we show that our algorithms for pathwidth and cutwidth are likely to be optimal, as improving them is equivalent to falsifying the pw-SETH.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

  1. [1]

    Pure Nash Equilibria in Graphical Games and Treewidth

    Antonis Thomas and Jan Van Leeuwen. Pure Nash Equilibria in Graphical Games and Treewidth . Algorithmica , 71(3):581--604, mar 2015

    work page 2015

  2. [35]

    Seymour and R

    P.D. Seymour and R. Thomas. Graph Searching and a Min-Max Theorem for Tree-Width . Journal of Combinatorial Theory, Series B , 58(1):22--33, may 1993. https://doi.org/10.1006/jctb.1993.1027 doi:10.1006/jctb.1993.1027

    work page doi:10.1006/jctb.1993.1027 1993

  3. [2]

    Computing Square Colorings on Bounded-Treewidth and Planar Graphs

    Akanksha Agrawal, D \'a niel Marx, Daniel Neuen, and Jasper Slusallek. Computing Square Colorings on Bounded-Treewidth and Planar Graphs . In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , Proceedings, pages 2087--2110. Society for Industrial and Applied Mathematics , jan 2023. https://doi.org/10.1137/1.9781611977554.c...

    work page doi:10.1137/1.9781611977554.ch80 2023

  4. [3]

    Grundy distinguishes treewidth from pathwidth

    R \' e my Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. SIAM J. Discret. Math. , 36(3):1761--1787, 2022. https://doi.org/10.1137/20m1385779 doi:10.1137/20m1385779

    work page doi:10.1137/20m1385779 2022

  5. [4]

    The complexity of computational problems about nash equilibria in symmetric win-lose games

    Vittorio Bil \` o and Marios Mavronicolas. The complexity of computational problems about nash equilibria in symmetric win-lose games. Algorithmica , 83(2):447--530, 2021. https://doi.org/10.1007/s00453-020-00763-x doi:10.1007/s00453-020-00763-x

    work page doi:10.1007/s00453-020-00763-x 2021

  6. [5]

    A new approach on locally checkable problems

    Flavia Bonomo-Braberman and Carolina Lucía Gonzalez. A new approach on locally checkable problems. Discrete Applied Mathematics , 314:53--80, 2022. URL: https://linkinghub.elsevier.com/retrieve/pii/S0166218X22000348, https://doi.org/10.1016/j.dam.2022.01.019 doi:10.1016/j.dam.2022.01.019

    work page doi:10.1016/j.dam.2022.01.019 2022

  7. [6]

    New complexity results about Nash equilibria

    Vincent Conitzer and Tuomas Sandholm. New complexity results about Nash equilibria. Games Econ. Behav. , 63(2):621--641, 2008. https://doi.org/10.1016/j.geb.2008.02.015 doi:10.1016/j.geb.2008.02.015

    work page doi:10.1016/j.geb.2008.02.015 2008

  8. [7]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

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

Show all 37 references
  1. [8]

    Fast hamiltonicity checking via bases of perfect matchings

    Marek Cygan, Stefan Kratsch, and Jesper Nederlof. Fast hamiltonicity checking via bases of perfect matchings. J. ACM , 65(3):12:1--12:46, 2018. https://doi.org/10.1145/3148227 doi:10.1145/3148227

    2018 doi

  2. [9]

    Papadimitriou

    Constantinos Daskalakis and Christos H. Papadimitriou. Computing pure nash equilibria in graphical games via markov random fields. In Joan Feigenbaum, John C. - I. Chuang, and David M. Pennock, editors, Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), Ann Arbor...

    2006 doi

  3. [10]

    Goldberg

    Edith Elkind, Leslie Ann Goldberg, and Paul W. Goldberg. Nash equilibria in graphical games on trees revisited. In Joan Feigenbaum, John C. - I. Chuang, and David M. Pennock, editors, Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), Ann Arbor, Michigan, USA, Ju...

    2006 doi

  4. [11]

    Goldberg

    Edith Elkind, Leslie Ann Goldberg, and Paul W. Goldberg. Computing good Nash equilibria in graphical games. In Jeffrey K. MacKie - Mason, David C. Parkes, and Paul Resnick, editors, Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, California, USA, Ju...

    2007 doi

  5. [12]

    Generalized graph packing problems parameterized by treewidth

    Baris Can Esmer and D \' a niel Marx. Generalized graph packing problems parameterized by treewidth. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025 , LIPIc...

    2025 doi

  6. [13]

    Pure nash equilibria: Hard and easy games

    Georg Gottlob, Gianluigi Greco, and Francesco Scarcello. Pure nash equilibria: Hard and easy games. J. Artif. Intell. Res. , 24:357--406, 2005. https://doi.org/10.1613/jair.1683 doi:10.1613/jair.1683

    2005 doi

  7. [14]

    Fixed-parameter complexity in AI and nonmonotonic reasoning

    Georg Gottlob, Francesco Scarcello, and Martha Sideri. Fixed-parameter complexity in AI and nonmonotonic reasoning. Artificial Intelligence , 138(1):55--86, 2002. URL: https://www.sciencedirect.com/science/article/pii/S0004370202001820, https://doi.org/10.1016/S0004-3702(02)00...

    2002 doi

  8. [15]

    On the complexity of constrained Nash equilibria in graphical games

    Gianluigi Greco and Francesco Scarcello. On the complexity of constrained Nash equilibria in graphical games. Theor. Comput. Sci. , 410(38-40):3901--3924, 2009. https://doi.org/10.1016/j.tcs.2009.05.030 doi:10.1016/j.tcs.2009.05.030

    2009 doi

  9. [16]

    The price of being partial: Complexity of partial generalized dominating set on bounded-treewidth graphs

    Jakob Greilhuber and D \' a niel Marx. The price of being partial: Complexity of partial generalized dominating set on bounded-treewidth graphs. CoRR , abs/2506.01645, 2025. https://arxiv.org/abs/2506.01645 arXiv:2506.01645 , https://doi.org/10.48550/arXiv.2506.01645 doi:10.48...

    2025 doi

  10. [17]

    The behavior of tree-width and path-width under graph operations and graph transformations

    Frank Gurski and Robin Weishaupt. The behavior of tree-width and path-width under graph operations and graph transformations. Algorithms , 18(7):386, 2025. https://doi.org/10.3390/a18070386 doi:10.3390/a18070386

    2025 doi

  11. [18]

    Computing L (p, 1)- Labeling with Combined Parameters

    Tesshu Hanaka, Kazuma Kawai, and Hirotaka Ono. Computing L (p, 1)- Labeling with Combined Parameters . In Ryuhei Uehara, Seok-Hee Hong, and Subhas C. Nandy, editors, WALCOM : Algorithms and Computation , pages 208--220, Cham, 2021. Springer International Publishing. https://do...

    2021 doi

  12. [19]

    Hedonic games and treewidth revisited

    Tesshu Hanaka and Michael Lampis. Hedonic games and treewidth revisited. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors, 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022 , LIPIcs, pages 64:1--6...

    2022 doi

  13. [20]

    Hartmann and D \' a niel Marx

    Tim A. Hartmann and D \' a niel Marx. Independence and domination on bounded-treewidth graphs: Integer, rational, and irrational distances. In Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, and Kim Thang Nguyen, editors, 42nd International Symposium on Theoretical Aspect...

    2025 doi

  14. [21]

    Pure nash equilibria: complete characterization of hard and easy graphical games

    Albert Xin Jiang and MohammadAli Safari. Pure nash equilibria: complete characterization of hard and easy graphical games. In Wiebe van der Hoek, Gal A. Kaminka, Yves Lesp \' e rance, Michael Luck, and Sandip Sen, editors, 9th International Conference on Autonomous Agents and ...

    2010

  15. [22]

    Improved ( In -) Approximability Bounds for d- Scattered Set

    Ioannis Katsikarelis, Michael Lampis, and Vangelis Paschos. Improved ( In -) Approximability Bounds for d- Scattered Set . Journal of Graph Algorithms and Applications , 27(3):219--238, may 2023. URL: https://jgaa.info/index.php/jgaa/article/view/paper621, https://doi.org/10.7...

    2023 doi

  16. [23]

    Kearns, Michael L

    Michael J. Kearns, Michael L. Littman, and Satinder Singh. Graphical models for game theory. In Jack S. Breese and Daphne Koller, editors, UAI '01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA,...

    2001

  17. [24]

    Multi-agent influence diagrams for representing and solving games

    Daphne Koller and Brian Milch. Multi-agent influence diagrams for representing and solving games. Games Econ. Behav. , 45(1):181--221, 2003. https://doi.org/10.1016/S0899-8256(02)00544-4 doi:10.1016/S0899-8256(02)00544-4

    2003 doi

  18. [25]

    Krumke, Madhav V

    Sven O. Krumke, Madhav V. Marathe, and S.S. Ravi. Models and Approximation Algorithms for Channel Assignment in Radio Networks . Wireless Networks , 7(6):575--584, nov 2001. https://doi.org/10.1023/A:1012311216333 doi:10.1023/A:1012311216333

    2001 doi

  19. [26]

    Minimum stable cut and treewidth

    Michael Lampis. Minimum stable cut and treewidth. 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 , LIPIcs, pages 92:1--9...

    2021 doi

  20. [27]

    First order logic on pathwidth revisited again

    Michael Lampis. First order logic on pathwidth revisited again. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn, Germany, July 10-14, 2023 , LIPIcs, pages 132:1--132:17....

    2023 doi

  21. [28]

    The Primal Pathwidth SETH

    Michael Lampis. The Primal Pathwidth SETH . In Proceedings of the 2025 Annual ACM - SIAM Symposium on Discrete Algorithms ( SODA ) , Proceedings, pages 1494--1564. Society for Industrial and Applied Mathematics, jan 2025. URL: https://epubs.siam.org/doi/10.1137/1.9781611978322...

    2025 doi

  22. [29]

    Circuits and backdoors: Five shades of the SETH

    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. ht...

    2026 doi

  23. [30]

    Structural parameterizations for induced and acyclic matching

    Michael Lampis and Manolis Vasilakis. Structural parameterizations for induced and acyclic matching. In Henning Fernau and Philipp Kindermann, editors, Graph-Theoretic Concepts in Computer Science - 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11-13, 2025, ...

    2025 doi

  24. [31]

    Papadimitriou and Binghui Peng

    Christos H. Papadimitriou and Binghui Peng. Public goods games in directed networks. Games Econ. Behav. , 139:161--179, 2023. https://doi.org/10.1016/j.geb.2023.02.002 doi:10.1016/j.geb.2023.02.002

    2023 doi

  25. [32]

    Graphical hedonic games of bounded treewidth

    Dominik Peters. Graphical hedonic games of bounded treewidth. In Dale Schuurmans and Michael P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA , pages 586--593. AAAI Press, 2016. https://do...

    2016 doi

  26. [33]

    Faster, higher, easier: Toward a systematic study of parameterized vertex and edge selection problems

    Philipp Schepper. Faster, higher, easier: Toward a systematic study of parameterized vertex and edge selection problems . PhD thesis, Saarländische Universitäts- und Landesbibliothek, 2025. URL: https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/40798, https://doi....

    2025 doi

  27. [34]

    Grant Schoenebeck and Salil P. Vadhan. The computational complexity of Nash equilibria in concisely represented games. ACM Trans. Comput. Theory , 4(2):4:1--4:50, 2012. https://doi.org/10.1145/2189778.2189779 doi:10.1145/2189778.2189779

    2012 doi

  28. [36]

    Pure Nash Equilibria in Graphical Games and Treewidth

    Antonis Thomas and Jan Van Leeuwen. Pure Nash Equilibria in Graphical Games and Treewidth . Algorithmica , 71(3):581--604, mar 2015. URL: http://link.springer.com/10.1007/s00453-014-9923-3, https://doi.org/10.1007/s00453-014-9923-3 doi:10.1007/s00453-014-9923-3

    2015 doi

  29. [37]

    Deciding morality of graphs is NP -complete

    Thomas Verma and Judea Pearl. Deciding morality of graphs is NP -complete. In David Heckerman and E. H. Mamdani, editors, UAI '93: Proceedings of the Ninth Annual Conference on Uncertainty in Artificial Intelligence, The Catholic University of America, Providence, Washington, ...

    1993

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.