Finding 3-Swap-Optimal Independent Sets and Dominating Sets is Hard
Open Access
- 15 February 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computation Theory
- Vol. 17 (1) , 1-31
Abstract
Local search problems consist of a set of feasible solutions, an objective function, and a neighborhood relation which assigns to each feasible solution a set of neighbors. A solution S is called locally optimal if none of its neighbors has a better objective value than S . For PLS-complete local search problems, there is presumably no polynomial-time algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and finding a better one if this is not the case can be done in polynomial time. We study local search for Weighted Independent Set and Weighted Dominating Set with the 3-swap neighborhood. The 3-swap neighborhood of a vertex set S in G is the collection of vertex sets which can be obtained from S by exchanging at most three vertices. On the negative side, the problem of finding a 3-swap-optimal independent set or dominating set is PLS-complete. Using the PLS-completeness for independent sets with the 3-swap-neighborhood, we also show PLS-completeness for a large class of maximum-weight subgraph problems. On the positive side, we show that locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3-swaps except (a) the swaps that remove two vertices from the current solution and add one vertex to the solution or (b) the swaps that remove one vertex from the current solution and add two vertices to the solution. This result is shown via general algorithms for subset-weight optimization problems with a restricted k -swap neighborhood.Keywords
Funding Information
- Deutsche Forschungsgemeinschaft (KO 3669/5-1)
This publication has 18 references indexed in Scilit:
- Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower BoundsSIAM Journal on Computing, 2020
- NuMWVC: A novel local search for minimum weighted vertex cover problemJournal of the Operational Research Society, 2019
- Finding near-optimal independent sets at scaleJournal of Heuristics, 2017
- A hybrid iterated local search heuristic for the maximum weight independent set problemOptimization Letters, 2017
- Fast local search for the maximum independent set problemJournal of Heuristics, 2012
- Simple Local Search Problems that are Hard to SolveSIAM Journal on Computing, 1991
- How easy is local search?Journal of Computer and System Sciences, 1988
- The node-deletion problem for hereditary properties is NP-completeJournal of Computer and System Sciences, 1980
- Reducibility among Combinatorial Problems1972
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970