Minimum Stable Cut and Treewidth.
Saved in:
| Title: | Minimum Stable Cut and Treewidth. |
|---|---|
| Authors: | Lampis, Michael1 |
| Source: | Discrete Mathematics & Theoretical Computer Science (DMTCS). 2026, Vol. 28 Issue 2, p1-28. 28p. |
| Subjects: | NP-hard problems, Computational complexity, Graph theory, Parameterization, Approximation algorithms |
| 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. 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 PLS-complete 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 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 (∆ · 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 NP-hard 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 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 + ε). 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| 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. 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 PLS-complete 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 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 (∆ · 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 NP-hard 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 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 + ε). 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 13658050 |
