Abstract | ||
---|---|---|
Abstract The multiple weighted hitting set problem is to find a subset of nodes in a hyper- graph that hits every hyperedge in at least m,nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m = 2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic,programming,algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected. Keywords: hitting set, job assignment, parameterized algorithms, dynamic programming on subsets, cores in graphs |
Year | DOI | Venue |
---|---|---|
2009 | 10.1007/978-3-540-85097-7_4 | Conference on Combinatorial Optimization and Applications |
Keywords | DocType | Volume |
Hitting set,Job assignment,Parameterized algorithms,Dynamic programming on subsets,Cores in graphs | Journal | 18 |
Issue | ISSN | Citations |
3 | 1382-6905 | 2 |
PageRank | References | Authors |
0.39 | 8 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Peter Damaschke | 1 | 471 | 56.99 |