CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Multiple hypernode hitting sets and smallest two-cores with targets

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
2nd International Conference on Combinatorial Optimization and Applications COCOA 2008, Lecture Notes in Computer Science Vol. 5165 (2008), p. 32-42.
[Konferensbidrag, refereegranskat]

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 it remains fixed-parameter tractable (FPT) for m=2, with the number of hyperedges as the parameter. This is accomplished by a nontrivial extension of the known dynamic programming algorithm for usual hypergraphs. The result might be of independent interest for assignment problems, but here we need it as an auxiliary result to solve a different problem motivated by network analysis: We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices in a graph, with the number of targets as the parameter. (A d-core is a subgraph where every vertex has degree at least d within the subgraph.) This FPT result is best possible, in the sense that an FPT algorithm for 3-cores cannot exist, for simple reasons.

Nyckelord: hitting set, fixed-parameter tractability, dynamic programming, cores in graphs

Denna post skapades 2008-09-03. Senast ändrad 2015-02-11.
CPL Pubid: 73482