I read somewhere that the problem of finding a k-edge connected spanning subgraph with the minimum number of edges is $ \mathcal{NP} $-hard in general. Is it the case for positive weighted graphs with "fractional subgraphs"?
More precisely, given an undirected graph $ G=(V,E) $ with $ c: E \to \mathbb{R}_+ $ edge weights or cost function. A cut is a partition of the vertices into two disjoint nonempty sets. The size/weight/cost of a cut is the sum of costs of edges having endpoints in different sets. A $ k $-edge connected graph is a graph which does not have a cut with size less than $ k $. The problem is to find a $ c_k $ cost function such that
- for each $ e \in E $ edge $ 0 \leq c_k(e) \leq c(e) $
- $ G $ with that $ c_k $ cost function is $ k $-edge connected
- the cost sum $ \sum_{e \in E} c_k(e) $ is minimum
So I think this problem is a relaxation of the unweighted case, since we do not have to select entire edges, we may use fractions of its weight as well. I give an example below:
The left graph is $G$ with $c$ cost function. The middle is an optimal $ c_1 $ solution with a total cost of $ 3 $ and the right is also $ 1 $-edge connected, but its total cost is $ 4 $, so not minimal. In contrast to the unweighted case $ c_1 $ is (almost) never a spanning tree (if $ G $ itself has a cycle).
My question is that the problem defined as above is $ \mathcal{NP} $-hard? If so could you give a reduction or a reference? If not is there any (not LP) algorithm to find such an optimal solution?
Thanks.