Can Local Optimality Be Used for Efficient Data Reduction?
Open Access
- 23 January 2025
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 69 (1) , 1-34
Abstract
An independent set S in a graph G is k-swap-optimal if there is no independent set $$S'$$ such that $$\varvec{|S'|>|S|}$$ and $$\varvec{|(S'\setminus S)\cup (S\setminus S')|\le k}$$ . Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap-optimal independent set or in all k-swap-optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are $$\varvec{\Sigma ^{\text {P}}_{2}}$$ -hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in $$\varvec{f(\Delta +k)\cdot n^{\mathcal {O}(1)}}$$ time whether it is in some k-optimal path.
Keywords
Funding Information
- Friedrich-Schiller-Universität Jena
This publication has 18 references indexed in Scilit:
- Distributed reconfiguration of maximal independent setsJournal of Computer and System Sciences, 2020
- Independent Set Reconfiguration Parameterized by Modular-WidthAlgorithmica, 2020
- Extension of Vertex Cover and Independent Set in Some Classes of Graphs2019
- Independent-set reconfiguration thresholds of hereditary graph classesDiscrete Applied Mathematics, 2018
- The Parameterized Complexity of Local Search for TSP, More RefinedAlgorithmica, 2012
- Local search: Is brute-force avoidable?Journal of Computer and System Sciences, 2012
- The disjoint paths problem in quadratic timeJournal of Combinatorial Theory, Series B, 2012
- Searching the k-change neighborhood for TSP is W[1]-hardOperations Research Letters, 2008
- How easy is local search?Journal of Computer and System Sciences, 1988
- A simplified NP-complete satisfiability problemDiscrete Applied Mathematics, 1984