CS Paper Radar

Multi-tier Flexible Graph Connectivity

Karthekeyan Chandrasekaran, Raymond Jiang, Krishna Kalathur

cs.DS ·submitted 2026-08-28 13:25 UTC · v2

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.77
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

Flexible Edge Cover: A Disjunctive Programming driven Approximation

cs.DS ·2026-11-06 ·Karthekeyan Chandrasekaran, Krishna Kalathur
hot direction similarity 0.71
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.

0.28

Approximation Algorithms for Multi-Criteria Network Design Problems

cs.DS ·2026-11-03 ·Mehrshad Taziki, Ali Vakilian
theoryhot direction similarity 0.70
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

A Simplified Analysis of the Good-Bad $3/2$-Approximation Algorithm for Some Minimum-Cost Graph Problems

cs.DS cs.DM ·2026-08-29 ·Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade
similarity 0.67
Abstract

In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected component has at least $k$ vertices. Couëtoux proves that the good-bad algorithm achieves a $3/2$-approximation for this problem. Davis and Williamson extend this result to the more general problem of finding a minimum-cost edge set that contains at least one edge from every cut $S\subseteq V$ satisfying $h(S) = 1$ where $h:2^V \rightarrow \{0,1\}$ is downward monotone; that is, $h(S) = 1$ implies $h(T) = 1$ for every nonempty subset $T \subseteq S$. The original problem corresponds to $h(S) =1$ when $|S|<k$. We give a simplified analysis of the good-bad algorithm for downward monotone functions.

0.10

Online Vertex Connectivity Augmentation

cs.DS ·2026-11-11 ·Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.66
Abstract · 35 pages

Network design problems form a classic subfield of online algorithms, but almost nothing is known about their more challenging vertex-connectivity variants. We initiate the study of online vertex-connectivity network design for arbitrary demand pairs by considering the fundamental problem of connectivity augmentation. In an instance of \emph{Online Vertex Connectivity Augmentation} (OVCA), we are given a $k$-vertex-connected graph $F$ and a set of additional purchasable edges (with costs). Demand pairs $(s_1,t_1),(s_2,t_2),\dots$ then arrive online. Upon each arrival, the algorithm must irrevocably purchase edges so that $s_i$ and $t_i$ become $(k{+}1)$-vertex-connected in the union of $F$ with all edges purchased so far. Our main contribution is an $O((k+\log n)\log n)$-competitive online algorithm for OVCA. We also give an offline $O(k+\log n)$-approximation algorithm. We obtain our algorithms via a structural dichotomy on the minimum vertex cuts of $F$. We note that some dependence on $k$ in the approximation ratio is necessary -- i.e., the problem is hard to approximate within any $\mathrm{polylog}(n)$ factor independent of $k$ -- which shows a separation from the edge-connectivity setting. Finally, specializing to $k=1$, our methods yield the first polylogarithmic-competitive online algorithm for a vertex-connectivity survivable network design problem, namely an $\widetilde O(\log^3 n)$-competitive algorithm for online $\{1,2\}$-VC-SNDP (i.e., an SNDP variant where each demand pair comes with a vertex-connectivity requirement of $1$ or $2$).

0.17

Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time

cs.DS ·2026-09-03 ·Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
similarity 0.66
Abstract

We study the multiobjective hypergraph min-cut problem: Given a hypergraph $H=(V,E)$ and $k$ cost functions $c_1, c_2, \ldots, c_k:E\to\mathbb{Z}_{\ge 0}$, the goal is to find a non-empty proper subset $U\subsetneq V$ of vertices with minimum $\max_{i\in [k]} c_i(δ(U))$. When $k$ is part of input, the problem is NP-hard (even in graphs). We focus on fixed-constant $k$ setting (e.g., $k=1, 2, 3, \ldots$). Single-objective hypergraph min-cut as well as multiobjective graph min-cut for a constant number of objectives admit polynomial-time algorithms. In contrast to these special cases, the complexity of multiobjective hypergraph min-cut remains open even for $k=2$. Known techniques fail to extend due to structural differences between graphs and hypergraphs. For $k$-objective hypergraph min-cut when $k$ is a fixed constant, we design a randomized PTAS, and two different randomized quasi-polynomial time algorithms. As an application of our $2$-objective hypergraph min-cut results, we obtain a quasi-polynomial time approximation scheme (QPTAS) for hypergraph connectivity interdiction. AI tools were used to iterate and refine the algorithmic ideas underlying this work.

0.25

Buy-at-Bulk Facility Location on Trees

cs.DS ·2026-08-26 ·Shamisa Nematollahi, Daniel Vaz
similarity 0.66
Abstract · Presented at WAOA 2025

We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+ε)$-approximation for any $ε> 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+ε$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.

0.28

Forbidden Subgraphs of Graphs with Low Bandwidth

cs.DS ·2026-09-01 ·Maria Chudnovsky, Daniel Lokshtanov, Eran Nevo
top venuetheory similarity 0.64
Abstract

A layout of a graph G is an injective function $f : V(G) \rightarrow Z$, and the bandwidth of a layout f is $bw(G,f) = max_{uv \in E(G)} |f(u) - f(v)|$. The bandwidth bw(G) of G is the minimum bandwidth of a layout of G. Computing the bandwidth of a graph is a notoriously hard problem: assuming P != NP, there is no polynomial time algorithm, even on very restricted classes of trees [Monien, SIAM Journal on Algebraic Discrete Methods, 1986], and no constant factor approximation, even on trees [Dubey et al., JCSS 2011]. Assuming the Exponential Time Hypothesis, there is no algorithm with running time $f(k)n^{o(k)}$ to determine whether an input graph has bandwidth at most k, even on very restricted classes of trees [Dregi and Lokshtanov, ICALP 2014]. In this paper we show that {\sc Bandwidth} on general graphs is FPT-approximable. In particular we give an algorithm that takes as input a graph G and an integer k, runs in time $2^{O(9^k)}n^{O(1)}$, and outputs a subtree T of G such that $bw(T) \geq k$ or a layout of G of bandwidth at most $(10^{85} k^{28})^{4^k}$. This resolves in the affirmative an open problem of Chung and Seymour [Discrete Mathematics, 1989], who asked whether the bandwidth of every graph G is upper bounded in terms of the maximum bandwidth of a subtree of G. Our theorem leads to a forbidden subgraph characterization for graphs of bounded bandwidth, and can be seen as an analog for bandwidth of the classic grid minor theorem for treewidth, the forbidden subtree theorem for pathwidth, and the forbidden subpath theorem for treedepth.

0.55