Can Local Optimality Be Used for Efficient Data Reduction?

An independent set S in a graph G is k-swap optimal if there is no independent set \(S'\) such that \(|S'|>|S|\) and \(|(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 \(\mathrm {\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 \(f(\varDelta +k)\cdot n^{\mathcal {O}(1)}\) time whether it is in some k-optimal path.