Abstract
A stable or locallyoptimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. Equivalently, a cut is stable if all vertices have the (weighted) majority of their neighbors on the other side. Finding a stable cut is a prototypical PLScomplete problem that has been studied in the context of local search and of algorithmic game theory.
In this paper we study Min Stable Cut, the problem of finding a stable cut of minimum weight, which is closely related to the Price of Anarchy of the Max Cut game. Since this problem is NPhard, we study its complexity on graphs of low treewidth, low degree, or both. We begin by showing that the problem remains weakly NPhard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this hardness with a pseudopolynomial DP algorithm solving the problem in time (Δ⋅ W)^{O(tw)}n^{O(1)}, where tw is the treewidth, Δ the maximum degree, and W the maximum weight. On the other hand, bounding Δ is also not enough, as the problem is NPhard for unweighted graphs of bounded degree. We therefore parameterize Min Stable Cut by both tw and Δ and obtain an FPT algorithm running in time 2^{O(Δ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(Δ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 almoststable 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+ε).
Motivated by these mostly negative results, we consider Unweighted Min Stable Cut. Here our results already imply a much faster exact algorithm running in time Δ^{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.
BibTeX  Entry
@InProceedings{lampis:LIPIcs.ICALP.2021.92,
author = {Lampis, Michael},
title = {{Minimum Stable Cut and Treewidth}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {92:192:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14161},
URN = {urn:nbn:de:0030drops141616},
doi = {10.4230/LIPIcs.ICALP.2021.92},
annote = {Keywords: Treewidth, Local MaxCut, Nash Stability}
}
Keywords: 

Treewidth, Local MaxCut, Nash Stability 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 