CS Paper Radar

Flexible Edge Cover: A Disjunctive Programming driven Approximation

Karthekeyan Chandrasekaran, Krishna Kalathur

cs.DS ·submitted 2026-11-06 20:08 UTC · v1
hot direction

Abstract

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 $p$ and $q$, and the goal is to find a minimum cost subset of edges such that each vertex has either at least $p$ safe edges incident to it or at least $p+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 $2$-approximation in all graphs. We show that the $2$-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)$-FGC) which has garnered much recent attention. For $(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)$-FGC.

Closest papers

Nearest neighbours by meaning across the whole index.

Multi-tier Flexible Graph Connectivity

cs.DS ·2026-08-28 ·Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur
similarity 0.71
Abstract

Motivated by non-uniform edge failures in network design, we introduce a multi-tier model of flexible graph connectivity. In k-tier Flexible Graph Connectivity (k-tier FGC), the input is an undirected graph G=(V, E) with non-negative edge costs, along with a classification of the edges into nested tiers T_1 subseteq T_2 subseteq ... subseteq T_k = E and non-negative integral tier requirements q_1 <= q_2 <= ... <= q_k. A non-empty proper subset R of vertices is safe if it is safe along one of the tiers, i.e., there exists i in [k] such that |delta(R) cap T_i| >= q_i. The goal is to find a minimum cost subset F subseteq E of edges such that the subgraph (V, F) has no unsafe cuts. The case of k=1 corresponds to the min-cost p-edge-connected spanning subgraph problem which is APX-hard. We design approximation algorithms for every fixed constant k for three variants of k-tier FGC: (i) for k-tier FGC, we design an LP-based logarithmic approximation, (ii) for min-cardinality k-tier FGC, we design a combinatorial approximation whose factor depends only on the tier requirements q_1 and q_k, and (iii) for k-tier Flexible Multi-Graph Connectivity, where we are allowed to use multiple copies of each edge while paying the cost of the edge for each chosen copy of the edge, we design an LP-based 2-approximation.

0.25

A $(p+q)^{O(pq)}$-approximation for $(p, q)$-Flexible Graph Connectivity

cs.DS ·2026-09-13 ·Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur
similarity 0.69
Abstract

In the $(p,q)$-Flexible Graph Connectivity problem, the input consists of non-negative integers $p$ and $q$ and a graph $G=(V, E)$ whose edges are classified into safe and unsafe edges with non-negative edge costs. A subgraph H of G is $(p,q)$-Flex-Connected if every non-empty proper subset of vertices has either at least $p$ safe edges or at least $p+q$ total edges crossing it. The goal is to find a minimum cost subset $F\subseteq E$ of edges such that the subgraph $(V, F)$ is $(p,q)$-Flex-Connected. We give a $(p+q)^{O(pq)}$-approximation for this problem, which in particular implies a constant approximation for every fixed constants $p$ and $q$. We achieve this by designing a $(p+q)^{O(pq)}$-approximation for the augmentation problem of finding a minimum cost subset of edges to add to make a (p,q-1)-Flex-Connected graph into a (p,q)-Flex-Connected graph. Underlying the augmentation algorithm is a structural result showing that all deficient cuts can be represented by min rooted-cuts in a $(p+q)^{pq}$-sized collection of digraphs. This structural result was discovered by ChatGPT Astra.

0.27

Approximation Algorithms for Multi-Criteria Network Design Problems

cs.DS ·2026-11-03 ·Mehrshad Taziki, Ali Vakilian
theoryhot direction similarity 0.64
Abstract

Min-max multi-criteria optimization asks for a single feasible solution minimizing the maximum of its costs under $\ell$ nonnegative cost functions, a formulation that captures both fairness across groups and robustness across scenarios. It has proved hard to approximate even for basic problems: for robust shortest paths, polylogarithmic approximations are known only in quasi-polynomial time. For network design, the best known guarantee is an $\ell$-approximation, which is tight for the natural LP relaxation. We show that exponentially better and nearly optimal guarantees are achievable for two fundamental network design problems. For multi-criteria connectivity augmentation (MC-CAP), which asks to increase the edge connectivity of a given undirected graph by one, we give a randomized polynomial-time $O(\log \ell)$-approximation algorithm. Applying our augmentation procedure iteratively and analyzing its randomized choices jointly across iterations yields an $O(\log k \log \ell)$-approximation for the multi-criteria $k$-edge-connected spanning subgraph (MC-$k$-ECSS) problem, for every $k \geq 2$. We complement these algorithms with a nearly matching lower bound: for every fixed $\varepsilon > 0$, MC-CAP admits no polynomial-time $O(\log^{1-\varepsilon} \ell)$-approximation, even when the underlying graph is a star, unless $\mathsf{NP}\subseteq\mathsf{DTIME}\bigl(n^{\log^{O(1)}n}\bigr)$. The same hardness extends to the MC-$k$-ECSS problem.

0.27

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization

cs.SI math.OCeess.SP ·2026-09-24 ·Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner, Kimmo Kansanen
benchmarktheory similarity 0.62
Abstract · 12 pages, 7 figures, 3 tables. Submitted to IEEE Transactions on Network Science and Engineering. A preliminary version of this work was pre…

Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.

0.21

The Strong Total Cover Problem

cs.DM cs.CCmath.CO ·2026-10-16 ·Manuel Aprile, Luca Ferrarini
similarity 0.62
Abstract · 28 pages, 4 figures

The Strong Total Cover Problem (STCP) is a novel covering problem defined on a graph $G = (V, E)$, where the objective is to find a minimum-cardinality subset $T \subseteq V \cup E$ such that every element of $V \cup E$ is covered. In this setting, a vertex covers itself and all its incident edges, while an edge covers itself together with its two endpoints. The STCP resembles classical covering problems such as Vertex Cover and Edge Cover problems, and naturally arises as the dual of the total matching problem. In this paper, we investigate the STCP from algorithmic, complexity, and polyhedral perspectives. We first establish close connections between STCP, the Dominating Set Problem, and the Maximum Induced Matching Problem. These relationships provide structural insights, imply the NP-hardness of STCP, and identify graph classes for which the problem is polynomial-time solvable. We then investigate the weighted version of STCP, showing that it remains NP-hard even on complete graphs with binary weights. On the other hand, we present a 2-approximation algorithm, and a polynomial-time algorithm for complete bipartite graphs. On the polyhedral side, we introduce the Strong Total Cover Polytope and derive several families of valid inequalities, some of which are shown to define facets. Finally, we provide a complete linear description of the associated polytope for triangular cactus graphs, revealing an interesting contrast with the considerably more intricate facial structure of the dominating set polytope on cactus graphs.

0.25

Emergency Vertex Cover

cs.DS ·2026-09-17 ·Eric Angel, Evangelos Bampas, Evripidis Bampis, Vincent Chau, Johanne Cohen +2 more
theory similarity 0.62
Abstract

The Minimum Vertex Cover problem is a fundamental combinatorial optimization problem, aiming to identify a minimum subset of vertices in a graph such that every edge is incident to at least one vertex in this subset. Among its variants, the Min-Power-Cover problem stands out due to its practical applications, such as camera placement at intersections: in an edge-weighted graph, an edge is covered if one of its endpoints is assigned a power value at least as large as the edge's weight. In this paper, we introduce the Emergency Vertex Cover (Em-VC) problem where an edge may be covered not only by its endpoints, but also by a distant vertex, provided the vertex is given sufficient power to "cover" the cumulative weight of the edges along a shortest path to one of the edge's endpoints plus the weight of the edge. Em-VC is motivated by different practical scenarios, e.g. the need for urban disaster response, where ensuring accessibility to all road segments (edges of the graph) is crucial for effective aid delivery. We prove that Em-VC is NP-hard, derive lower bounds, and design a polynomial-time algorithm for its continuous version. Moreover, we present a 4/3-approximation algorithm for the discrete case and identify several special graph classes for which the problem can be solved in polynomial time.

0.42

Minimum Sum Vertex Cover via Minimum Vertex Cover

cs.DS cs.DM ·2026-09-22 ·Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak, Michiel Smid
theory similarity 0.61
Abstract

The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered. We study the problem through the structure of vertex covers and obtain new approximation and exact algorithms, together with conditional lower bounds. For graphs of maximum degree $Δ$, we show that a simple ordering algorithm based on a minimum vertex cover achieves approximation ratio $R_Δ\le {(\sqrtΔ+1)}/{2}$. For $d$-regular graphs, we give a polynomial-time $1.184$-approximation by combining Max-$k$-Vertex-Cover approximation with a structural bound on optimal prefixes. On the exact side, we give an algorithm parameterized by the vertex cover number $k$ running in $2^{O(k\log k)} + O(n+m)$ time, improving the previous dependence on $k$, where $n$ and $m$ are the number of vertices and edges in the graph, respectively. We also develop a separator-based exact algorithm running in $ 2^{O(\sqrt n \log n)}$ time on planar, bounded-genus, and fixed-minor-free graph classes. Finally, we prove that Minimum Sum Vertex Cover is NP-hard on planar graphs and, assuming ETH, admits no $2^{o(\sqrt n)}$-time exact algorithm on $n$-vertex planar graphs. Thus our planar upper bound is tight up to logarithmic factors in the exponent.

0.20

The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem

cs.CC math.OC ·2026-09-03 ·Avinash Bhardwaj
similarity 0.60
Abstract

The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing exactness for weighted graphs and left the unweighted case open. We show that recognition is NP-complete even for connected simple unweighted graphs, and hence strongly NP-complete for nonnegative integer edge weights. The reduction provides an explicit SDP optimum and makes the additive integrality gap equal to the minimum number of unsatisfied clauses in the source formula. Recognition remains NP-complete even when an exact rational optimal primal--dual pair is supplied. We also establish strong NP-hardness of recognizing exactness of the Frieze--Jerrum Max-$k$-Cut relaxation for every fixed $k\ge3$, even for connected graphs with nonnegative integer edge weights. An independent bounded-weight construction gives a second proof for Max-Cut. Finally, reductions preserving the additive gap up to explicit factors establish strong NP-completeness of exactness recognition for a basic Max-DiCut SDP and NP-hardness for a Max-Bisection SDP.

0.33