Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
Bazgan, Cristina; Toubaline, Sónia; Tuza, Zsolt (2011), Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures, in Smyth, William F., Combinatorial Algorithms 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, Springer : Berlin Heidelberg, p. 154-166. 10.1007/978-3-642-19222-7_17
TypeCommunication / Conférence
Conference countryUNITED KINGDOM
Book titleCombinatorial Algorithms 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
Book authorSmyth, William F.
MetadataShow full item record
Abstract (EN)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.
Subjects / Keywordscograph; independent set; complexity; NP-hard; ptas; bipartite graph; bounded treewidth; most vital nodes
Showing items related by title and author.
Bazgan, Cristina; Toubaline, Sónia; Vanderpooten, Daniel (2013) Article accepté pour publication ou publié