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 \geq 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.