The problem of computing a 2-T-connected spanning subgraph with minimum number of edges in directed graphs

2024/09/29 by Raed Jaberi, Jaberi, Raed, Reham Mansour +1
Computer Science · Engineering · #Interconnection Networks and Systems #VLSI and Analog Circuit Testing #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.2409.19773

Abstract

Let G=(V,E) be a strongly connected graph with |V|≥ 3. For T⊆ V, the strongly connected graph G is 2-T-connected if G is 2-edge-connected and for each vertex w in T, w is not a strong articulation point. This concept generalizes the concept of 2-vertex connectivity when T contains all the vertices in G. This concept also generalizes the concept of 2-edge connectivity when |T|=0. The concept of 2-T-connectivity was introduced by Durand de Gevigney and Szigeti in 2018. In this paper, we prove that there is a polynomial-time 4-approximation algorithm for the following problem: given a 2-T-connected graph G=(V,E), identify a subset E^ 2T ⊆ E of minimum cardinality such that (V,E^2T) is 2-T-connected.

Related

• Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
• A 4/3 Approximation for 2-Vertex-Connectivity
• Minimum 2-edge strongly biconnected spanning directed subgraph problem
• Improved Approximation for Two-Edge-Connectivity
• Minimum 2-vertex-twinless connected spanning subgraph problem