跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 pp and qq, and the goal is to find a minimum cost subset of edges such that each vertex has either at least pp safe edges incident to it or at least p+qp+q total edges incident to it. We show that FLEX-EDGE-COVER is APX-hard in simple bipartite graphs. A greedy approach leads to a 22-approximation in all graphs. We show that the 22-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 (p,q)(p,q)-FGC) which has garnered much recent attention. For (p,q)(p,q)-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 (p,q)(p,q)-FGC.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 pp and qq, and the goal is to find a minimum cost subset of edges such that each vertex has either at least pp safe edges incident to it or at least p+qp+q total edges incident to it. We show that FLEX-EDGE-COVER is APX-hard in simple bipartite graphs. A greedy approach leads to a 22-approximation in all graphs. We show that the 22-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 (p,q)(p,q)-FGC) which has garnered much recent attention. For (p,q)(p,q)-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 (p,q)(p,q)-FGC.

查看此版本解读 →查看此版本原文 ↗