Problems related to strong connectivity and strong biconnectivity
2026-06-15 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study a special kind of network (called a strong biconnected graph) where removing certain points still leaves it strongly connected. They want to find the smallest set of connections that keeps these properties intact. They show how to find an approximate solution in a reasonable amount of time, guaranteeing the solution is at most seven times larger than the smallest possible one. This helps in efficiently maintaining robust networks.
strongly connected graphbiconnected graphsubgraphapproximation algorithmpolynomial timegraph connectivityedge subsetnetwork robustness
Authors
Raed Jaberi
Abstract
Let $G=(V,E)$ be a strong biconnected graph and let $B \subseteq V$ such that for each vertex $w \in B$, the subgraph $G \setminus \lbrace w\rbrace$ is strongly connected. In this paper we study the problem of computing a subset $E_β \subseteq E$ of minimum size such that the subgraph $G_β=(V,E_β)$ is strongly biconnected and for each vertex $w \in B$, the subgraph $G_β \setminus \lbrace w\rbrace$ is strongly connected. We prove that there exists a polynomial time $7$-approximation algorithm for this problem.