Paper Info
Title
Complexity of most vital nodes for independent set in graphs related to tree structures
Abstract
Given an undirected graph with weights on its vertices, the k most vital nodes independent set problem consists of determining a set of k vertices whose removal results in the greatest decrease in the maximum weight of independent sets. We also consider the complementary problem, minimum node blocker independent set that consists of removing a subset of vertices of minimum size such that the maximum weight of independent sets in the remaining graph is at most a specified value. We show that these problems are NP-hard on bipartite graphs but polynomial-time solvable on unweighted bipartite graphs. Furthermore, these problems are polynomial also on graphs of bounded treewidth and cographs. A result on the non-existence of a ptas is presented, too.
Year
DOI
Venue
2010
10.1007/978-3-642-19222-7_17
IWOCA
Keywords
DocType
Volume
minimum node blocker,vital node,tree structure,bipartite graph,independent set problem,k vertex,minimum size,undirected graph,remaining graph,complementary problem,independent set,maximum weight,interdiction,np hard,polynomial time,approximation,algorithm,cograph,complexity
Conference
6460
ISSN
Citations 
PageRank 
0302-9743
5
0.55
References 
Authors
12
3
Name
Order
Citations
PageRank
Cristina Bazgan167962.76
Sonia Toubaline2607.54
Zsolt Tuza31889262.52