pith. sign in

arxiv: 2104.13097 · v4 · submitted 2021-04-27 · 💻 cs.CC · cs.DS

Minimum Stable Cut and Treewidth

Michael Lampis This is my paper

Pith reviewed 2026-05-24 13:42 UTC · model grok-4.3

classification 💻 cs.CC cs.DS
keywords minimum stable cuttreewidthpathwidthexponential time hypothesisparameterized complexitydynamic programmingNP-hardnessapproximation scheme
0
0 comments X

The pith

Finding a minimum stable cut requires time exponential in pathwidth times degree unless the ETH fails.

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

The paper establishes that Minimum Stable Cut cannot be solved substantially faster than its natural dynamic programming algorithms when parameterized by treewidth or pathwidth. It gives a pseudo-polynomial algorithm running in time roughly (Delta W) to the power O(tw) and an FPT algorithm in 2 to the O(Delta tw) times poly, then proves matching lower bounds under the Exponential Time Hypothesis that hold even when treewidth is replaced by the smaller parameter pathwidth. A reader would care because the results pin down the precise interaction between treewidth, degree, and weights needed for tractability on this locally optimal version of the cut problem.

Core claim

The paper claims that there is no algorithm for weighted Minimum Stable Cut running in (nW)^{o(pw)} time or in 2^{o(Delta pw)}(n + log W)^{O(1)} time unless the ETH is false, and that the same holds for the unweighted case with no n^{o(pw)} algorithm; these lower bounds apply even when the parameter is pathwidth rather than treewidth. The paper also supplies an FPT approximation scheme for almost-stable cuts parameterized by treewidth.

What carries the argument

The ETH-hardness reduction that produces equivalent Minimum Stable Cut instances while preserving pathwidth and maximum degree.

If this is right

  • The pseudo-polynomial DP running in (Delta W)^{O(tw)} n^{O(1)} time is optimal up to the precise exponent.
  • The FPT algorithm running in 2^{O(Delta tw)}(n + log W)^{O(1)} time is optimal up to the precise exponent.
  • For unweighted graphs the algorithm running in Delta^{O(tw)} n^{O(1)} time is optimal up to the precise exponent.
  • An FPT approximation scheme exists for almost-stable cuts when parameterized only by treewidth.

Where Pith is reading between the lines

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

  • Local stability constraints do not appear to simplify the parameterized complexity of cut problems below that of ordinary min-cut.
  • Similar ETH lower bounds may apply to other graph problems whose solutions are required to be locally optimal under single-vertex moves.
  • The existence of an FPT approximation scheme for almost-stable cuts suggests that modest relaxations of stability can restore tractability even when exact stability does not.

Load-bearing premise

The ETH-based reductions correctly preserve both pathwidth and maximum degree while mapping stable-cut instances to stable-cut instances.

What would settle it

An algorithm that solves unweighted Minimum Stable Cut in n^{o(pw)} time on graphs of pathwidth pw, or weighted Minimum Stable Cut in (nW)^{o(pw)} time, would falsify the ETH.

read the original abstract

A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem of finding a stable cut of minimum weight. Since this problem is NP-hard, we study its complexity on graphs of low treewidth, low degree, or both. We begin by showing that the problem remains weakly NP-hard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this hardness with a pseudo-polynomial DP algorithm solving the problem in time $(\Delta\cdot W)^{O(tw)}n^{O(1)}$, where $tw$ is the treewidth, $\Delta$ the maximum degree, and $W$ the maximum weight. On the other hand, bounding $\Delta$ is also not enough, as the problem is NP-hard for unweighted graphs of bounded degree. We therefore parameterize Minimum Stable Cut by both $tw$ and $\Delta$ and obtain an FPT algorithm running in time $2^{O(\Delta tw)}(n+\log W)^{O(1)}$. Our main result for the weighted problem is to provide a reduction showing that both aforementioned algorithms are essentially optimal, even if we replace treewidth by pathwidth: if there exists an algorithm running in $(nW)^{o(pw)}$ or $2^{o(\Delta pw)}(n+\log W)^{O(1)}$, then the ETH is false. Complementing this, we show that we can, however, obtain an FPT approximation scheme parameterized by treewidth, if we consider almost-stable solutions, that is, solutions where no single vertex can unilaterally increase the weight of its incident cut edges by more than a factor of $(1+\varepsilon)$. Motivated by these mostly negative results, we consider Unweighted Minimum Stable Cut. Here our results already imply a much faster exact algorithm running in time $\Delta^{O(tw)}n^{O(1)}$. We show that this is also probably essentially optimal: an algorithm running in $n^{o(pw)}$ would contradict the ETH.

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.

Referee Report

0 major / 1 minor

Summary. The paper studies Minimum Stable Cut (finding a minimum-weight stable cut, where no single vertex flip increases the cut weight) on graphs of bounded treewidth (tw) and/or maximum degree (Δ). It proves weak NP-hardness even on trees; gives a pseudo-polynomial DP in time (Δ·W)^{O(tw)} n^{O(1)}; an FPT algorithm in 2^{O(Δ tw)}(n+log W)^{O(1)}; ETH-based lower bounds showing these are tight even when tw is replaced by pathwidth (pw) while preserving Δ; an FPT (1+ε)-approximation scheme for almost-stable cuts; and, for the unweighted case, a Δ^{O(tw)} n^{O(1)} algorithm with an n^{o(pw)} ETH lower bound.

Significance. If the results hold, they tightly characterize the complexity of Minimum Stable Cut, showing that both tw and Δ are necessary for tractability and that the given algorithms are ETH-optimal (even for pw). Strengths include the use of standard tree-decomposition DP and ETH reductions that preserve the relevant parameters; the almost-stable FPT approximation provides a positive counterpart to the mostly negative exact results. These are load-bearing contributions to parameterized complexity of local-search problems.

minor comments (1)
  1. The abstract states that the ETH reductions preserve pathwidth and maximum degree while mapping stable-cut instances to stable-cut instances; the full manuscript should include an explicit statement (e.g., in the hardness section) confirming that the reduction does not increase Δ or pw by more than a constant factor.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive evaluation, including the recommendation to accept. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained against external ETH

full rationale

The paper derives FPT algorithms via standard dynamic programming on tree decompositions (time bounds expressed directly in terms of tw, Δ, W) and establishes conditional lower bounds via explicit reductions from ETH-hard problems (e.g., 3-SAT variants) that preserve pathwidth and maximum degree while mapping stable-cut instances to stable-cut instances. These reductions are constructed in the paper but rely on the independent ETH assumption rather than any quantity defined from the paper's own outputs or fitted parameters. No self-citations are load-bearing for the central claims, no ansatzes are smuggled, and no renaming of known results occurs. The derivation chain is therefore independent of its own results.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on the standard Exponential Time Hypothesis for its lower bounds and on the correctness of dynamic programming over tree decompositions; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to obtain the lower bounds stated in the final two paragraphs of the abstract.
  • standard math Standard properties of tree decompositions and path decompositions
    Used throughout the algorithmic and hardness sections referenced in the abstract.

pith-pipeline@v0.9.0 · 5910 in / 1484 out tokens · 20805 ms · 2026-05-24T13:42:19.569068+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

57 extracted references · 57 canonical work pages · 1 internal anchor

  1. [1]

    Grundy coloring & friends, half-graphs, bicliques

    Pierre Aboulker, \' E douard Bonnet, Eun Jung Kim, and Florian Sikora. Grundy coloring & friends, half-graphs, bicliques. In STACS , volume 154 of LIPIcs , pages 58:1--58:18. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    work page 2020

  2. [2]

    Parameterized power vertex cover

    Eric Angel, Evripidis Bampis, Bruno Escoffier, and Michael Lampis. Parameterized power vertex cover. Discret. Math. Theor. Comput. Sci. , 20(2), 2018. URL: http://dmtcs.episciences.org/4873

    work page 2018

  3. [3]

    Local max-cut in smoothed polynomial time

    Omer Angel, S \' e bastien Bubeck, Yuval Peres, and Fan Wei. Local max-cut in smoothed polynomial time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017 , pages 429--437. ACM , 2017. https://doi.org/10.1145/3055399.3055...

    work page doi:10.1145/3055399.3055402 2017

  4. [4]

    Arkin, Michael A

    Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, and Steven Skiena. The lazy bureaucrat scheduling problem. Inf. Comput. , 184(1):129--146, 2003

    work page 2003

  5. [5]

    Inapproximability of NP -complete variants of Nash equilibrium

    Per Austrin, Mark Braverman, and Eden Chlamtac. Inapproximability of NP -complete variants of Nash equilibrium. Theory Comput. , 9:117--142, 2013. https://doi.org/10.4086/toc.2013.v009a003 doi:10.4086/toc.2013.v009a003

    work page doi:10.4086/toc.2013.v009a003 2013

  6. [6]

    Mirrokni, and Alexander Skopalik

    Baruch Awerbuch, Yossi Azar, Amir Epstein, Vahab S. Mirrokni, and Alexander Skopalik. Fast convergence to nearly optimal solutions in potential games. In Lance Fortnow, John Riedl, and Tuomas Sandholm, editors, Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008 , pages 264--273. ACM , 2008. https://doi.org/1...

    work page doi:10.1145/1386790.1386832 2008

  7. [7]

    Exact algorithms for partial curve matching via the Fr´ echet distance

    Maria - Florina Balcan, Avrim Blum, and Yishay Mansour. Improved equilibria via public service advertising. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009 , pages 728--737. SIAM , 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496850

    work page arXiv 2009

  8. [8]

    Bazgan, L

    C. Bazgan, L. Brankovic, K. Casel, H. Fernau, K. Jansen, K.-M. Klein, M. Lampis, M. Liedloff, J. Monnot, and V. T. Paschos. The many facets of upper domination. Theoretical Computer Science , 717:2--25, 2018

    work page 2018

  9. [9]

    Grundy distinguishes treewidth from pathwidth

    R \' e my Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi. Grundy distinguishes treewidth from pathwidth. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference) , volume 173 of LIPIcs , pages 14:1--14:19. Schloss ...

    work page doi:10.4230/lipics.esa.2020.14 2020

  10. [10]

    Parameterized (approximate) defective coloring

    R \' e my Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (approximate) defective coloring. SIAM J. Discret. Math. , 34(2):1084--1106, 2020. https://doi.org/10.1137/18M1223666 doi:10.1137/18M1223666

    work page doi:10.1137/18m1223666 2020

  11. [11]

    On some tighter inapproximability results (extended abstract)

    Piotr Berman and Marek Karpinski. On some tighter inapproximability results (extended abstract). In Jir \' Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings , volume 1644 of Lecture Notes in Computer Science , pag...

    work page doi:10.1007/3-540-48523-6 1999

  12. [12]

    Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games

    Anand Bhalgat, Tanmoy Chakraborty, and Sanjeev Khanna. Approximating pure Nash equilibrium in cut, party affiliation, and satisfiability games. In David C. Parkes, Chrysanthos Dellarocas, and Moshe Tennenholtz, editors, Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010 , pages 73--82. ACM , 20...

    work page doi:10.1145/1807342.1807353 2010

  13. [13]

    Improving the smoothed complexity of FLIP for max cut problems

    Ali Bibak, Charles Carlson, and Karthekeyan Chandrasekaran. Improving the smoothed complexity of FLIP for max cut problems. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019 , pages 897--916. SIAM , 2019. https://doi.org/10.1137/1.978161197548...

    work page doi:10.1137/1.9781611975482.55 2019

  14. [14]

    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. CoRR , abs/1907.10468, 2019. URL: http://arxiv.org/abs/1907.10468, http://arxiv.org/abs/1907.10468 arXiv:1907.10468

    work page internal anchor Pith review Pith/arXiv arXiv 1907

  15. [15]

    Bodlaender and Torben Hagerup

    Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput. , 27(6):1725--1746, 1998

    work page 1998

  16. [16]

    Bonnet, M

    \' E . Bonnet, M. Lampis, and V. T. Paschos. Time-approximation trade-offs for inapproximable problems. Journal of Computer and System Sciences , 92:171 -- 180, 2018

    work page 2018

  17. [17]

    Approximating the best Nash equilibrium in n\( ^ o \) \( ^ (log n) \)-time breaks the exponential time hypothesis

    Mark Braverman, Young Kun - Ko, and Omri Weinstein. Approximating the best Nash equilibrium in n\( ^ o \) \( ^ (log n) \)-time breaks the exponential time hypothesis. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015 , pages 970--982. SIAM , 2015. http...

    work page doi:10.1137/1.9781611973730.66 2015

  18. [18]

    Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure

    Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games: Existence, efficient computation, and structure. ACM Trans. Economics and Comput. , 3(1):2:1--2:32, 2015. https://doi.org/10.1145/2614687 doi:10.1145/2614687

    work page doi:10.1145/2614687 2015

  19. [19]

    Smoothed complexity of local max-cut and binary max- CSP

    Xi Chen, Chenghao Guo, Emmanouil - Vasileios Vlatakis - Gkaragkounis, Mihalis Yannakakis, and Xinzhi Zhang. Smoothed complexity of local max-cut and binary max- CSP . In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, ...

    work page doi:10.1145/3357713.3384325 2020

  20. [20]

    Mirrokni, and Anastasios Sidiropoulos

    George Christodoulou, Vahab S. Mirrokni, and Anastasios Sidiropoulos. Convergence and approximation in potential games. Theor. Comput. Sci. , 438:13--27, 2012. https://doi.org/10.1016/j.tcs.2012.02.033 doi:10.1016/j.tcs.2012.02.033

    work page doi:10.1016/j.tcs.2012.02.033 2012

  21. [21]

    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

  22. [22]

    6 Josep Díaz, Olli Pottonen, Maria J

    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

  23. [23]

    Inapproximability results for constrained approximate Nash equilibria

    Argyrios Deligkas, John Fearnley, and Rahul Savani. Inapproximability results for constrained approximate Nash equilibria. Inf. Comput. , 262(Part):40--56, 2018. https://doi.org/10.1016/j.ic.2018.06.001 doi:10.1016/j.ic.2018.06.001

    work page doi:10.1016/j.ic.2018.06.001 2018

  24. [24]

    (in)approximability of maximum minimal FVS

    Louis Dublois, Tesshu Hanaka, Mehdi Khosravian Ghadikolaei, Michael Lampis, and Nikolaos Melissinos. (in)approximability of maximum minimal FVS . In ISAAC , volume 181 of LIPIcs , pages 3:1--3:14. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2020

    work page 2020

  25. [25]

    Louis Dublois, Michael Lampis, and Vangelis Th. Paschos. Upper dominating set: Tight algorithms for pathwidth and sub-exponential approximation. CoRR , abs/2101.07550, 2021. URL: https://arxiv.org/abs/2101.07550, http://arxiv.org/abs/2101.07550 arXiv:2101.07550

    work page arXiv 2021

  26. [26]

    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, June 11-15, 2006 , pages 100--109. ACM , 2006. https://doi.org/10.1145/1134707.113...

    work page doi:10.1145/1134707.1134719 2006

  27. [27]

    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, June 11-15, 2007 , pages 162--171. ACM , 2007. https://doi.org/10.1145/1250910.125...

    work page doi:10.1145/1250910.1250935 2007

  28. [28]

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

    Robert Els \" a sser and Tobias Tscheuschner. Settling the complexity of local max-cut (almost) completely. In Luca Aceto, Monika Henzinger, and Jir \' Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I , volume 6755 of Lecture Notes in Computer Science ...

    work page doi:10.1007/978-3-642-22006-7 2011

  29. [29]

    Parameterized Algorithms for Maximum Cut with Connectivity Constraints

    Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints . In IPEC 2019 , pages 13:1--13:15, 2019

    work page 2019

  30. [30]

    Smoothed analysis of local search for the maximum-cut problem

    Michael Etscheid and Heiko R \" o glin. Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms , 13(2):25:1--25:12, 2017. https://doi.org/10.1145/3011870 doi:10.1145/3011870

    work page doi:10.1145/3011870 2017

  31. [31]

    Papadimitriou, and Kunal Talwar

    Alex Fabrikant, Christos H. Papadimitriou, and Kunal Talwar. The complexity of pure Nash equilibria. In L \' a szl \' o Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004 , pages 604--612. ACM , 2004. https://doi.org/10.1145/1007352.1007445 doi:10.1145/1007352.1007445

    work page doi:10.1145/1007352.1007445 2004

  32. [32]

    u cken, Germany (Virtual Conference) , volume 168 of LIPIcs , pages 50:1--50:19. Schloss Dagstuhl - Leibniz-Zentrum f \

    Dimitris Fotakis, Vardis Kandiros, Thanasis Lianeas, Nikos Mouzakis, Panagiotis Patsilinakos, and Stratis Skoulakis. Node-max-cut and the complexity of equilibrium in linear weighted congestion games. In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 20...

    work page doi:10.4230/lipics.icalp.2020.50 2020

  33. [33]

    Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul G

    Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul G. Spirakis. The structure and complexity of Nash equilibria for a selfish routing game. Theor. Comput. Sci. , 410(36):3305--3326, 2009. https://doi.org/10.1016/j.tcs.2008.01.004 doi:10.1016/j.tcs.2008.01.004

    work page doi:10.1016/j.tcs.2008.01.004 2009

  34. [34]

    Furini, I

    F. Furini, I. Ljubić, and M. Sinnl. An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem. European Journal of Operational Research , 262(2):438--448, 2017

    work page 2017

  35. [35]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP -Completeness . W. H. Freeman, 1979

    work page 1979

  36. [36]

    Nash and correlated equilibria: Some complexity considerations

    Itzhak Gilboa and Eitan Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior , 1(1):80--93, 1989

    work page 1989

  37. [37]

    On strong equilibria in the max cut game

    Laurent Gourv \` e s and J \' e r \^ o me Monnot. On strong equilibria in the max cut game. In Stefano Leonardi, editor, Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings , volume 5929 of Lecture Notes in Computer Science , pages 608--615. Springer, 2009. https://doi.org/10.1007/978-3-642...

    work page doi:10.1007/978-3-642-10841-9 2009

  38. [38]

    The lazy bureaucrat problem with common arrivals and deadlines: Approximation and mechanism design

    Laurent Gourv \` e s, J \' e r \^ o me Monnot, and Aris Pagourtzis. The lazy bureaucrat problem with common arrivals and deadlines: Approximation and mechanism design. In FCT , volume 8070 of Lecture Notes in Computer Science , pages 171--182. Springer, 2013

    work page 2013

  39. [39]

    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

    work page doi:10.1016/j.tcs.2009.05.030 2009

  40. [40]

    Bodlaender, Tom C

    Tesshu Hanaka, Hans L. Bodlaender, Tom C. van der Zanden, and Hirotaka Ono. On the maximum weight minimal separator. Theoretical Computer Science , 796:294 -- 308, 2019

    work page 2019

  41. [41]

    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, September 5-9, 2022, Berlin/Potsdam, Germany , volume 244 of LIPIcs , pages 64:1--64:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 202...

    work page doi:10.4230/lipics.esa.2022.64 2022

  42. [42]

    How hard is it to approximate the best Nash equilibrium? SIAM J

    Elad Hazan and Robert Krauthgamer. How hard is it to approximate the best Nash equilibrium? SIAM J. Comput. , 40(1):79--91, 2011. https://doi.org/10.1137/090766991 doi:10.1137/090766991

    work page doi:10.1137/090766991 2011

  43. [43]

    Which problems have strongly exponential complexity? J

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci. , 63(4):512--530, 2001. https://doi.org/10.1006/jcss.2001.1774 doi:10.1006/jcss.2001.1774

    work page doi:10.1006/jcss.2001.1774 2001

  44. [44]

    An improved algorithm for parameterized edge dominating set problem

    Ken Iwaide and Hiroshi Nagamochi. An improved algorithm for parameterized edge dominating set problem. J. Graph Algorithms Appl. , 20(1):23--58, 2016

    work page 2016

  45. [45]

    Johnson, Christos H

    David S. Johnson, Christos H. Papadimitriou, and Mihalis Yannakakis. How easy is local search? J. Comput. Syst. Sci. , 37(1):79--100, 1988. https://doi.org/10.1016/0022-0000(88)90046-3 doi:10.1016/0022-0000(88)90046-3

    work page doi:10.1016/0022-0000(88)90046-3 1988

  46. [46]

    Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. Discret. Appl. Math. , 264:90--117, 2019. https://doi.org/10.1016/j.dam.2018.11.002 doi:10.1016/j.dam.2018.11.002

    work page doi:10.1016/j.dam.2018.11.002 2019

  47. [47]

    Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structurally parameterized d-scattered set. Discrete Applied Mathematics , 2020. URL: http://www.sciencedirect.com/science/article/pii/S0166218X20301517, https://doi.org/10.1016/j.dam.2020.03.052 doi:10.1016/j.dam.2020.03.052

    work page doi:10.1016/j.dam.2020.03.052 2020

  48. [48]

    Weighted upper edge cover: Complexity and approximability

    Kaveh Khoshkhah, Mehdi Khosravian Ghadikolaei, J \' e r \^ o me Monnot, and Florian Sikora. Weighted upper edge cover: Complexity and approximability. J. Graph Algorithms Appl. , 24(2):65--88, 2020

    work page 2020

  49. [49]

    Parameterized approximation schemes using graph widths

    Michael Lampis. Parameterized approximation schemes using graph widths. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I , volume 8572 of Lecture Notes in Computer Science , pages ...

    work page doi:10.1007/978-3-662-43948-7 2014

  50. [50]

    Treewidth with a quantifier alternation revisited

    Michael Lampis and Valia Mitsou. Treewidth with a quantifier alternation revisited. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th International Symposium on Parameterized and Exact Computation, IPEC 2017, September 6-8, 2017, Vienna, Austria , volume 89 of LIPIcs , pages 26:1--26:12. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2017. ...

    work page doi:10.4230/lipics.ipec.2017.26 2017

  51. [51]

    Efficient maximal cubic graph cuts (extended abstract)

    Martin Loebl. Efficient maximal cubic graph cuts (extended abstract). In Javier Leach Albert, Burkhard Monien, and Mario Rodr \' guez - Artalejo, editors, Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings , volume 510 of Lecture Notes in Computer Science , pages 351--362. Springer, 199...

    work page doi:10.1007/3-540-54233-7 1991

  52. [52]

    Small clique detection and approximate Nash equilibria

    Lorenz Minder and Dan Vilenchik. Small clique detection and approximate Nash equilibria. In Irit Dinur, Klaus Jansen, Joseph Naor, and Jos \' e D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, ...

    work page doi:10.1007/978-3-642-03685-9 2009

  53. [53]

    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. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12400

    work page 2016

  54. [54]

    Integer linear programs and local search for max-cut

    Svatopluk Poljak. Integer linear programs and local search for max-cut. SIAM J. Comput. , 24(4):822--839, 1995. https://doi.org/10.1137/S0097539793245350 doi:10.1137/S0097539793245350

    work page doi:10.1137/s0097539793245350 1995

  55. [55]

    Sch \" a ffer and Mihalis Yannakakis

    Alejandro A. Sch \" a ffer and Mihalis Yannakakis. Simple local search problems that are hard to solve. SIAM J. Comput. , 20(1):56--87, 1991. https://doi.org/10.1137/0220004 doi:10.1137/0220004

    work page doi:10.1137/0220004 1991

  56. [56]

    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

    work page doi:10.1145/2189778.2189779 2012

  57. [57]

    M. Zehavi. Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics , 31(4):2440--2456, 2017

    work page 2017