NP-hardness of the Sparsest k-Subgraph Problem in Chordal Graphs
Résumé
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.
Origine | Fichiers produits par l'(les) auteur(s) |
---|