← 研踪 PaperTrailarXiv:2611.10189 · v1
Flexible Edge Cover: A Disjunctive Programming driven Approximation
首次提交 2026-11-07 04:08
版本更新 2026-11-07 04:08
雷达观测 2026-11-10 10:11
摘要
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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 04:08 · 最新观测版本
Flexible Edge Cover: A Disjunctive Programming driven Approximation
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.
查看此版本解读 →查看此版本原文 ↗