Transversals of subtree hypergraphs and the source location problem in digraphs

Heuvel van den, Jan; Johnson, M.

doi:10.1002/net.20206

Transversals of subtree hypergraphs and the source location problem in digraphs

Heuvel van den, Jan; Johnson, M.

Authors

Jan Heuvel van den

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Abstract

A hypergraph H = (V,E) is a subtree hypergraph if there is a tree T on V such that each hyperedge of E induces a subtree of T. Since the number of edges of a subtree hypergraph can be exponential in n = |V|, one can not always expect to be able to find a minimum size transversal in time polynomial in n. In this paper, we show that if it is possible to decide if a set of vertices W ⊆ V is a transversal in time S(n) (where n = |V|), then it is possible to find a minimum size transversal in O(n3S(n)). This result provides a polynomial algorithm for the Source Location Problem: a set of (k,l)-sources for a digraph D = (V,A) is a subset S of V such that for any v ∈ V there are k arc-disjoint paths that each join a vertex of S to v and l arc-disjoint paths that each join v to S. The Source Location Problem is to find a minimum size set of (k,l)-sources. We show that this is a case of finding a transversal of a subtree hypergraph, and that in this case S(n) is polynomial.

Citation

Heuvel van den, J., & Johnson, M. (2008). Transversals of subtree hypergraphs and the source location problem in digraphs. Networks, 51(2), 113-119. https://doi.org/10.1002/net.20206

Journal Article Type	Article
Publication Date	Mar 1, 2008
Deposit Date	Oct 7, 2008
Publicly Available Date	Dec 11, 2015
Journal	Networks
Print ISSN	0028-3045
Electronic ISSN	1097-0037
Publisher	Wiley
Peer Reviewed	Peer Reviewed
Volume	51
Issue	2
Pages	113-119
DOI	https://doi.org/10.1002/net.20206
Keywords	Graphs, Hypergraphs, Source location, Algorithms.

Files

Accepted Journal Article (174 Kb)
PDF

Copyright Statement
This is the accepted version of the following article: van den Heuvel, J. and Johnson, M. (2008), Transversals of subtree hypergraphs and the source location problem in digraphs. Networks, 51(2): 113-119, which has been published in final form at http://dx.doi.org/10.1002/net.20206. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.