Premium
Transversals of subtree hypergraphs and the source location problem in digraphs
Author(s) -
van den Heuvel Jan,
Johnson Matthew
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20206
Subject(s) - hypergraph , transversal (combinatorics) , digraph , combinatorics , disjoint sets , vertex (graph theory) , mathematics , time complexity , join (topology) , set (abstract data type) , polynomial , tree (set theory) , discrete mathematics , path (computing) , graph , computer science , mathematical analysis , programming language
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 ( n 3 S ( 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. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008