A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem

Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh

In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc dis…