Can Local Optimality Be Used for Efficient Data Reduction?
Christian Komusiewicz, Nils Morawietz · Theory of Computing Systems · 2025
Abstract An independent set S in a graph G is k-swap-optimal if there is no independent set $$S'$$ S ′ such that $$\varvec{|S'|>|S|}$$ | S ′ | > | S | and $$\varvec{|(S'\setminus S)\cup (S\setminus S')|\le k}$$ | ( S ′ \ S ) ∪ ( S \ S ′ ) | ≤ 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}}$$ Σ 2 P -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)}}$$ f ( Δ + k ) · n O ( 1 ) time whether it is in some k-optimal path.