Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2004-10

May 2004

Transversals of Subtree Hypergraphs and the Source Location Problem in Digraphs

Jan van den Heuvel and Matthew Johnson


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. To find a minimum size transversal for a subtree hypergraph is, in general, NP-hard. In this paper, we show that if it is possible to decide if a set of vertices W in 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 K of V such that for any v in V\K there are k arc-disjoint paths that each join a vertex of K to v and l arc-disjoint paths that each join v to K. 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.

A PDF file (192 kB) with the full contents of this report can be downloaded by clicking here.

(This paper supersedes the earlier paper A Polynomial Algorithm for the Source Location Problem in Digraphs, which is obsolete.)

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2004-10, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@cdam.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html