NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs
Abstract
Given a simple undirected graph G = (V,E) and an integer k ≤ |V|, the k-sparsest subgraph problem asks for a set of k vertices which induce the minimum number of edges. Whereas its special case independent set and many other optimization problems become polynomial-time solvable in chordal graphs, we show that k-sparsest subgraph remains NP-hard in this graph class.
Origin | Files produced by the author(s) |
---|
Loading...