CS Paper Radar

On Eternal Connected Vertex Cover

Rajat Adak, Saraswati Girish Nanoti

cs.DM math.CO ·submitted 2026-09-30 06:43 UTC · v1
theory

Abstract

For a connected graph $G$ with at least one edge, the \textit{eternal connected vertex cover} number $ecvc(G)$ is the minimum number of guards that can maintain a connected vertex cover after every response to an arbitrary sequence of edge attacks. Denote the minimum size of a connected vertex cover by $cvc(G)$. It is known that $cvc(G)\leq ecvc(G)\leq cvc(G)+1$. A necessary condition for $ecvc(G)=cvc(G)$ is that every vertex belongs to some minimum connected vertex cover. We show that this condition is not sufficient: there exists a $32$-vertex graph $G$ that has $cvc(G)=19$ and $ecvc(G)=20$, although every vertex of $G$ belongs to some minimum connected vertex cover. For connected graphs with minimum degree at least two, we establish the sharp bound $cvc(G)\geq 2|V(G)|-|E(G)|-1$ and $\mathcal F$ denotes the class attaining equality. We prove that $G\in\mathcal F$ if and only if the vertices of degree at least three induce a forest. Within $\mathcal F$, the conditions $ecvc(G)=cvc(G)$, membership of every vertex in some minimum connected vertex cover, and the presence of at least two degree-two vertices on every cycle are equivalent. As applications, we obtain $ecvc(G)=cvc(G)$ for full subdivisions of connected graphs of minimum degree at least two and for minimally $2$-connected graphs. In both the families, every minimum connected vertex cover is an eternally winning configuration. This is not true in general for graphs outside $\mathcal{F}$, we show one example of such a graph.

Closest papers

Nearest neighbours by meaning across the whole index.

Structural Parameterizations for Eternal Vertex Cover

cs.DM cs.CCcs.DSmath.CO ·2026-09-15 ·Neeldhara Misra, Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki
similarity 0.69
Abstract · An extended abstract of this work has been accepted and presented to IPEC 2026

Eternal Vertex Cover (EVC) is a turn-based attacker-defender game on an undirected graph $G$. To begin with, the defender places $k$ guards on vertices of $G$. The attacker, on their turn, can choose an edge $e$ not already occupied at both endpoints to "attack". The edge $e$ is defended if a guard moves along the edge $e$. The defender, on their turn, can move any subset of guards. A guard can only move to a neighboring vertex. The minimum number of guards needed to indefinitely defend against any sequence of attacks is called the eternal vertex cover number, generalizing the classic vertex cover number. Determining this number is NP-hard in general, motivating the study of parameterized and approximation algorithms. The problem is known to be FPT when parameterized by the cover number, but structural parameters remain relatively unexplored in the literature. In this work, we explore structural parameterizations for EVC. We show that EVC is FPT parameterized by the cluster vertex deletion number, which generalizes the previously studied parameterization by vertex cover number. We next study the problem parameterized by vertex integrity, which is the smallest number of vertices we need to delete from $G$ so that the resulting graph is a disjoint union of constant-sized components. We first show that Eternal Vertex Cover is XP parameterized by vertex integrity. Then, we develop a polynomial-time approximation algorithm, which computes an additive $6k+1$ ($g(k)$) approximation, where $k$ is equal to the cluster vertex deletion number (vertex integrity). Finally, we show a FPT algorithm for when the deletion set produces "nice" connected components, which are components that are bounded in size and satisfy a technical condition.

0.34

Exploring Minimal Blocking Sets for Kernelization Lower Bounds for $\mathcal{F}$-Minor Deletion

cs.DS cs.CC ·2026-10-13 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
similarity 0.63
Abstract · Full version of an IPEC 2026 contribution. Abstract has been shortened for arXiv

For Vertex Cover, a minimal blocking set of a graph $G$ is an inclusion-wise minimal vertex set contained in no minimum vertex cover of $G$. Bougeret et al. [SIDMA 2022] showed that, for all minor-closed graph classes $\mathcal{G}$, Vertex Cover has a polynomial kernel parameterized by the distance to $\mathcal{G}$ if and only if $\mathcal{G}$ has bounded minimal blocking sets. In this work, we explore how far this connection between minimal blocking sets and kernelization extends to $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$. A minimal $\mathcal{F}$-blocking set of $G$ is a minimal vertex set not contained in any optimal $\mathcal{F}$-Minor Deletion solution of $G$. For connected families $\mathcal{F}$, we show that if some graph class $\mathcal{G}$ closed under disjoint union has unbounded minimal $\mathcal{F}$-blocking sets, then $\mathcal{F}$-Minor Deletion parameterized by the deletion distance to $\mathcal{G}$ has no polynomial kernel. This generalizes a result of Hols et al. [SIDMA 2022] for Vertex Cover. We then show that this criterion does not capture all kernelization lower bounds for $\mathcal{F}$-Minor Deletion, even for minor-closed graph classes. Motivated by the work of Dekker and Jansen [Discrete Appl. Math. 2024], we study the more general notion of extended $\mathcal{F}$-blocking sets and the kernelization lower bounds they yield. For every fixed integer $η\geq 1$, Pw-$η$ Deletion is the problem of deleting at most $k$ vertices to reduce the pathwidth to at most $η$. We show that it has no polynomial kernel parameterized by the distance to graphs with pathwidth at most $η+1$. Moreover, for connected families $\mathcal{F}$, we show that $\mathcal{F}$-Minor Deletion parameterized by the distance to graphs with pathwidth at most $\max_{F\in\mathcal{F}} pw(F)+1$ has no polynomial kernel.

0.26

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

Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors

cs.DS cs.DCcs.DM ·2026-10-07 ·Saeed Amiri, Sebastian Siebertz
theory similarity 0.62
Abstract

For every fixed proper minor-closed class $\mathscr C$ and every $ε>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+ε)γ_f(G)$ on every $G\in\mathscr C$. Here $a(\mathscr C)$ is the supremum edge-to-vertex ratio in $\mathscr C$, and $γ_f(G)$ is the fractional domination number. The class also admits a deterministic $(1+ε)$-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most $(1+ε)γ(G)$. In each case, the number of rounds depends only on $\mathscr C$ and $ε$. None of these algorithms requires the number of vertices or the maximum degree as part of the input. For planar graphs, this gives the deterministic guarantee $(7+ε)γ_f(G)$. Together with the lower bound of Hilke, Lenzen and Suomela, it determines the infimum of the deterministic constant-round approximation ratios for planar minimum dominating set as $7$, settling a question that had remained open since their work. The corresponding infima, measured against the integral optimum, are $7$ for graphs of Euler genus at most any fixed $g\ge0$, $2t-3$ for $K_t$-minor-free graphs with $3\le t\le9$, and $2r+1$ for graphs of treewidth or pathwidth at most any fixed $r\ge1$. We also prove that, for every integer $r\ge1$, no deterministic constant-round LOCAL algorithm achieves an approximation ratio below $2r+1$ on the $r$-th powers of paths, even when every vertex knows the number of vertices. This gives a new proof that the limiting constants are optimal for planar graphs, graphs of bounded treewidth or pathwidth, and $K_t$-minor-free graphs with $3\le t\le9$. For triangle-free planar graphs, the corresponding infimum is $5$.

0.32

A Counterexample to Teschner's Bondage-Number Conjecture

cs.DM math.CO ·2026-09-01 ·Yousof Yavari
theory similarity 0.62
Abstract · 9 pages, no figures; complete Python 3 verifier included in the appendix

For a finite simple graph $G$ with at least one edge, the bondage number $b(G)$ is the least number of edges whose deletion increases the domination number $γ(G)$. Teschner conjectured that $b(G)\le \tfrac32Δ(G)$ for every graph $G$. We disprove this conjecture by giving a connected cubic bipartite graph on eighteen vertices with \[ γ(G)=6 \qquad\text{and}\qquad b(G)=5. \] The domination number is established by a complete counting argument across the bipartition. An explicit five-edge deletion raises the domination number from six to seven. For the matching lower bound, we give an exact finite certificate: the graph has 297 minimum dominating sets, and deleting any one of its $\binom{27}{4}=17{,}550$ four-edge subsets leaves at least one of those sets dominating. The enumeration is deterministic, uses only exact integer and set operations, and is reproduced by the complete standard-library verifier included in the appendix.

0.21

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

Subexponential algorithms for structural parameterizations of Vertex Cover in geometric graphs

cs.DS ·2026-11-16 ·Marin Bougeret, Juan Pablo Bravo, Daniel Gonçalves
theory similarity 0.62
Abstract · 43 pages, 8 figures, submitted

A number of recent works have investigated the existence of parameterized subexponential algorithms in geometric graph classes for hitting a fixed small graph as a subgraph or as a minor. In this setting, given an $n$-vertex graph, the goal is to decide in time $n^{O(1)}2^{o(k)}$ if a solution of size at most $k$ exists. Inspired by recent results in kernelization for structural parameters, we investigate subexponential algorithms for the Vertex Cover (VC) problem, but parameterized by distance-to-triviality instead of solution size. More formally, given a fixed "trivial" graph class $\mathcal{C}$, the problem takes as input $(G,X,k)$, where $G \setminus X \in \mathcal{C}$, and asks if $G$ admits a vertex cover of size at most $k$. Our goal is to design algorithms for this problem running in time $n^{O(1)}2^{o(|X|)}$. The motivation is that, since $|X|$ is typically arbitrarily smaller than $k$, such algorithms might be faster than ETH-tight subexponential algorithms parameterized by $k$. We identify two sets of sufficient conditions under which the problem admits a subexponential algorithm: one for the case where $\mathcal{C}$ is the class of paths, and another for the case where $\mathcal{C}$ is the class of graphs of constant treedepth. We also provide two applications of these algorithmic results: we prove that $s$-string graphs and pseudo-disk graphs satisfy the first set of conditions, whereas string graphs satisfy the second set. The two sets share a common condition that might be of independent interest, as it implies a property that bounds the treewidth of any string graph in terms of a given modulator to a fixed graph class $\mathcal{C}$. Finally, concerning more restricted graph classes having the $ASQGM(ω)$ property (such as map graphs and $H$-minor free graphs), we prove a dichotomy, depending on the maximum treewidth in $\mathcal{C}$.

0.14

Almost tight distributed approximation for domination in sparse graph classes

cs.DC cs.DMcs.DS ·2026-10-22 ·Timothé Picavet
similarity 0.62
Abstract · 27 pages, 4 figures

We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\varepsilon>0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\varepsilon$, which is optimal up to $\varepsilon$ for every even integer $d\geq 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\varepsilon)$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\varepsilon)$-approximations for their triangle-free subclasses. This answers the $7+\varepsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\varepsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\varepsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.

0.33