Dual Half-integrality for Uncrossable Cut Cover and its Application to Maximum Half-Integral Flow

Naveen Garg, Nikhil Kumar

Given an edge weighted graph and a forest $F$, the $\text{2-edge connectivity augmentation problem}$ is to pick a minimum weighted set of edges, $E^{\prime }$, such that every connected c…