SciEnggJ. 2023 16 (2) 291-309

available online: August 18, 2023

*Corresponding author

Email Address: alfonso.labao@upd.edu.ph

Date received: April 2, 2023

Date revised: May 23, 2023

Date accepted: August 15, 2023

Survivable Network Design with Constrained h-Subgraph Flows

Alfonso B. Labao* and Henry N. Adorna

University of the Philippines, Diliman, Quezon City, 1101, Philippines

In this paper, we propose a variant of the survivable network design problem, where subgraphs are given flow constraints, which represent upper bounds on weights of outgoing edges with endpoints that belong to vertex subsets of these subgraphs. The general problem of verifying whether the weights of outgoing edges of any vertex subset (i.e. a graph cut) of an arbitrary subgraph meets a certain upper bound is a computationally hard problem. However, our proposed problem considers special types of subgraphs (termed h-subgraphs) which possess a tree structure. In particular, a h-subgraph consists of a trunk whose vertices are connected by a unique path and which are termed as trunk vertices. Each trunk vertex is connected to a branch which also has a tree structure. This special graph structure of h-subgraphs - along with conditions over the flow constraint function and additional constraints on the optimization problem allow for the construction of a polynomial-time algorithm to solve our proposed problem - using efficient separation oracles under the ellipsoid method of linear programming. Our proposed algorithm provides (2pl,2z(S)+3)-performance where p is the maximum length of any path that connects the root and leaves of a branch of any h-subgraph, l is the maximum number of leaves of any branch of a h-subgraph, and S is a vertex subset of a branch of a h-subgraph.

**© 2024 SciEnggJPhilippine-American Academy of Science and Engineering**