pipette
ESEspañol

Flexible Edge Cover: A Disjunctive Programming driven Approximation

Karthekeyan Chandrasekaran, Krishna Kalathur

Preprint

In the authors' words

We introduce the flexible edge cover problem, denoted FLEX-EDGE-COVER: the input here is an undirected graph with non-negative edge costs along with a partition of the edges into safe and unsafe edges, non-negative integers and , and the goal is to find a minimum cost subset of edges such that each vertex has either at least safe edges incident to it or at least total edges incident to it. We show that FLEX-EDGE-COVER is APX-hard in simple bipartite graphs. A greedy approach leads to a -approximation in all graphs. We show that the -factor can be improved in simple graphs via a novel disjunctive programming-based LP formulation. AI-tools were used in the analysis of our rounding algorithm. Our motivation for introducing and investigating FLEX-EDGE-COVER is its close connection to the Flexible Graph Connectivity problem (denoted -FGC) which has garnered much recent attention. For -FGC, we develop a tighter LP-formulation via the disjunctive programming approach. We hope that our disjunctive-programming based LP and rounding algorithms for FLEX-EDGE-COVER will serve as a starting point towards a constant factor approximation for -FGC.

Main resultLimitation the authors admit

Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.