Finding One Local Optimum Is Easy -- but What About Two?
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917146030768128 |
|---|---|
| author | Kobayashi, Yasuaki Kurita, Kazuhiro Yamaguchi, Yutaro |
| author_facet | Kobayashi, Yasuaki Kurita, Kazuhiro Yamaguchi, Yutaro |
| contents | The class PLS (Polynomial Local Search) captures the complexity of finding a solution that is locally optimal and has proven to be an important concept in the theory of local search. It has been shown that local search versions of various combinatorial optimization problems, such as Maximum Independent Set and Max Cut, are complete for this class. Such computational intractability typically arises in local search problems allowing arbitrary weights; in contrast, for unweighted problems, locally optimal solutions can be found in polynomial time under standard settings. In this paper, we pursue the complexity of local search problems from a different angle: We show that computing two locally optimal solutions is NP-hard for various natural unweighted local search problems, including Maximum Independent Set, Minimum Dominating Set, Max SAT, and Max Cut. We also discuss several tractable cases for finding two (or more) local optimal solutions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07524 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding One Local Optimum Is Easy -- but What About Two? Kobayashi, Yasuaki Kurita, Kazuhiro Yamaguchi, Yutaro Data Structures and Algorithms Computational Complexity The class PLS (Polynomial Local Search) captures the complexity of finding a solution that is locally optimal and has proven to be an important concept in the theory of local search. It has been shown that local search versions of various combinatorial optimization problems, such as Maximum Independent Set and Max Cut, are complete for this class. Such computational intractability typically arises in local search problems allowing arbitrary weights; in contrast, for unweighted problems, locally optimal solutions can be found in polynomial time under standard settings. In this paper, we pursue the complexity of local search problems from a different angle: We show that computing two locally optimal solutions is NP-hard for various natural unweighted local search problems, including Maximum Independent Set, Minimum Dominating Set, Max SAT, and Max Cut. We also discuss several tractable cases for finding two (or more) local optimal solutions. |
| title | Finding One Local Optimum Is Easy -- but What About Two? |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2507.07524 |