Remarks on the Complexity of Signed $k$-Independence on Graphs

Abstract

This paper is motivated by the concept of the signed $k$-independence problem and dedicated to the complexity of the problem on graphs. We show that the problem is linear-time solvable for any strongly chordal graph with a strong elimination ordering and polynomial-time solvable for distance-hereditary graphs. For any fixed positive integer $k\ge 1$, we show that the signed $k$-independence problem on chordal graphs and bipartite planar graphs is NP-complete. Furthermore, we show that even when restricted to chordal graphs or bipartite planar graphs, the signed $k$-independence problem, parameterized by a positive integer $k$ and weight $\kappa$, is not fixed-parameter tractable.