Source location problems considering vertex‐connectivity and edge‐connectivity simultaneously

Abstract

Abstract Let G = ( V , E ) be an undirected multigraph, where V and E are a set of vertices and a set of edges, respectively. Let k and l be fixed nonnegative integers. This paper considers location problems of finding a minimum‐size vertex‐subset S ⊆ V such that for each vertex x ∈ V the vertex‐connectivity between S and x is greater than or equal to k and the edge‐connectivity between S and x is greater than or equal to l . For the problem with edge‐connectivity requirements, that is, k = 0, an O ( L (| V |, | E |, l )) time algorithm is already known, where L (| V |, | E |, l ) is the time to find all h ‐edge‐connected components for h = 1, 2, … , l and O ( L (| V |, | E |, l )) = O (| E | + | V | 2 + | V |min{| E |, l | V |}min{ l , | V |}) is known. In this paper, we show that the problem with k ≥ 3 is NP‐hard even for l = 0. We then present an O ( L (| V |, | E |, l )) time algorithm for 0 ≤ k ≤ 2 and l ≥ 0. Moreover, we prove that the problem parameterized by the size of S is fixed‐parameter tractable (FPT) for k = 3 and l ≥ 0. © 2002 Wiley Periodicals, Inc.