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.
