Multiple hypernode hitting sets and smallest two-cores with targets |
| |
Authors: | Peter Damaschke |
| |
Institution: | (1) School of Computer and Systems Sciences, Jawaharlal Nehru University, New Delhi, India |
| |
Abstract: | The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph 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: | |
本文献已被 SpringerLink 等数据库收录! |
|