کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431762 | 688624 | 2006 | 15 صفحه PDF | دانلود رایگان |
We introduce an NP-complete special case of the Weighted Set Cover problem and show its fixed-parameter tractability with respect to the maximum subset size, a parameter that appears to be small in relevant applications. More precisely, in this practically relevant variant we require that the given collection C of subsets of a base set S should be “tree-like”. That is, the subsets in C can be organized in a tree T such that every subset one-to-one corresponds to a tree node and, for each element s of S, the nodes corresponding to the subsets containing s induce a subtree of T . This is equivalent to the problem of finding a minimum edge cover in an edge-weighted acyclic hypergraph. Our main result is an algorithm running in O(k3⋅mn)O(3k⋅mn) time where k denotes the maximum subset size, n:=|S|n:=|S|, and m:=|C|m:=|C|. The algorithm also implies a fixed-parameter tractability result for the NP-complete Multicut in Trees problem, complementing previous approximation results. Our results find applications in computational biology in phylogenomics and for saving memory in tree decomposition based graph algorithms.
Journal: Journal of Discrete Algorithms - Volume 4, Issue 4, December 2006, Pages 608–622