The paper disproves a prior FPT algorithm for PNE in graphical games of bounded treewidth, proves W[1]-hardness, and gives improved algorithms with matching pw-SETH lower bounds for pathwidth and cutwidth.
New complexity results about Nash equilibria
2 Pith papers cite this work, alongside 211 external citations. Polarity classification is still indexing.
2
Pith papers citing it
211
external citations · OpenAlex
verdicts
ACCEPT 2representative citing papers
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.
citing papers explorer
-
Pure Nash Equilibria in Graphical Games of Bounded Width Revisited
The paper disproves a prior FPT algorithm for PNE in graphical games of bounded treewidth, proves W[1]-hardness, and gives improved algorithms with matching pw-SETH lower bounds for pathwidth and cutwidth.
-
Minimum Stable Cut and Treewidth
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.