CS Paper Radar

Fractional distance-edge-monitoring in lexicographic products

Xiumin Wang, Minglei Mao, Yaping Mao, Ralf Klasing

cs.DM ·submitted 2026-11-08 13:36 UTC · v1
theory

Abstract

We give an exact formula for the fractional distance-edge-monitoring number of $G\circ H$, where $G$ is connected of order $m\ge2$ and $H$ has order $n\ge2$. By the previously established endpoint-monitoring property, the fractional monitoring program reduces to fractional vertex cover, whose linear-programming dual is fractional matching. Writing $d_c(H)$ for the critical difference of $H$, we obtain $\operatorname{dem}_{f}(G\circ H)=(mn-D(G,H))/2$, where $D(G,H)=\max_{A\in\mathcal{I}(G)}\bigl(d_c(H)|A|-n|N_G(A)|\bigr)$ and $\mathcal{I}(G)$ denotes the family of all independent sets of $G$, including the empty set, while $N_G(A)$ is the open neighborhood of $A$. This formula characterizes the products attaining $mn/2$ and gives an equality criterion for the fractional matching lower bound of Ma, Cheng, Mao and Wang. Under the stated hypotheses, the lower bound of Ma et al. is attained if and only if either factor has a fractional perfect matching or $H$ is edgeless. Two outer trees show that the factor orders and fractional matching numbers do not determine the product value.

Closest papers

Nearest neighbours by meaning across the whole index.

A sharp higher-order Cheeger inequality

cs.DS math.COmath.SP ·2026-09-28 ·Yunpeng Li
theory similarity 0.57
Abstract

Let $λ_k(G)$ be the $k$th eigenvalue of the normalized Laplacian of a finite undirected weighted graph $G$ with positive degrees, where $k$ is an integer satisfying $1\le k\le |V(G)|$. Let $\varphi_k(G)$ be the minimum possible maximum conductance of $k$ disjoint nonempty vertex sets. We prove $\varphi_k(G)\le C\sqrt{λ_k(G)\log(k+1)}$ for an absolute constant $C$. The number of sets and the spectral index are both $k$, and conductance is measured in the original graph. The logarithmic dependence is optimal up to an absolute constant. The proof combines geometric partitioning of the spectral embedding with minimum-cut improvement and adaptive projections in coefficient space. A single conductance threshold is used throughout the construction. The resulting maps have disjoint supports, and the sum of their Gram matrices is bounded below by an absolute positive multiple of the identity. A dyadic maximal estimate bounds the sum of their internal energies uniformly over unit coefficient vectors. A dimension argument using local eigenvalues then yields exactly $k$ disjoint sparse cuts.

0.05

Optimal radio labelings for the Cartesian product of a path and the Heawood graph

cs.DM math.CO ·2026-11-10 ·Payal Vasoya, Miral Doshi, Devsi Bantva
theory similarity 0.57
Abstract · 24 pages, 1 figures

For a simple graph $G$, let $d(u,v)$ denote the distance between two vertices $u$ and $v$ in $G$, and let $diam(G)$ denote the diameter of $G$. A radio labeling of $G$ is a mapping $f : V(G) \rightarrow \mathbb{N} \cup \{0\}$ such that $|f(u)-f(v)|\geq diam(G) + 1 - d(u,v)$ holds for every pair of distinct vertices $u, v \in G$. The span of $f$ is the difference between the largest and smallest integers assigned by $f$, and the radio number $rn(G)$ is the minimum span taking over all radio labelings of $G$. Let $P_n$ denote the path on $n$ vertices and let $H$ denote the Heawood graph (see Figure-1). In this paper we determine the radio number for the Cartesian product of a path and the Heawood graph, and characterize all optimal radio labelings of $P_n \Box H$. Moreover, we show that the radio number of $P_n \Box H$ exceed the lower bound given for $rn(G)$ in [6], where $G$ is any graph, and that this gap is arbitrarily large.

0.27

Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate

cs.DS ·2026-10-01 ·Yaowei Long
top venue similarity 0.57
Abstract · 80 pages, to appear in FOCS 2026

We present new algorithms for the vertex-failure distance oracles and labeling schemes problems in undirected weighted graphs. A vertex-failure distance oracle is a data structure that, given two vertices $x$ and $y$ and a failed vertex set $F$ of size at most $f$, returns an approximation to the distance between $x$ and $y$ in $G \setminus F$. In the labeling-scheme setting, the data structure needs to be stored distributively as labels on the vertices, and each query $(x,y,F)$ must be answered by accessing only the labels of the vertices in $F \cup \{x,y\}$. For any $f\geq 1$ and $k \ge 1$, we obtain a vertex-failure distance oracle with $O(k^{6})$ approximation, space $\tilde{O}(f^{2}n^{1+1/k})$, query time $\tilde{O}(f^{5}n^{1/k})$, and polynomial preprocessing time. In particular, this is the first time-efficient oracle for multiple vertex failures with space close to linear, as well as the first constant-approximation oracle with polynomial space when tolerating $Ω(\log n)$ vertex failures. The previous results, due to [Duan-Gu-Ren, SODA'21], gave two alternatives: for any constant $c \ge 1$ and $ε>0$, one oracle has $\mathrm{poly}(\log n,f)$ approximation, space $n^{2+1/c}\mathrm{poly}(\log n,f)$, and query time $\mathrm{poly}(\log n,f^{c})$, while the other has $(1+ε)$ approximation, space $n^{2+1/c}(\log n/ε)^{O(f)}$, and query time $\mathrm{poly}(\log n,f^{c},1/ε)$. We also obtain a vertex-failure distance labeling scheme with $O(k^{6})$ approximation and label size $f^{3}n^{1/k}\log^{O(k)} n$. This is the first nontrivial distance labeling scheme for vertex failures. Our techniques build on recent tools related to length-constrained vertex expanders and also introduce a new expander-based shortcut sparsification. The latter also leads to a deterministic vertex-failure connectivity labeling scheme of size $\tilde{O}(f^{2})$.

0.32

Graph Similarity Meets Optimal Transport

cs.DM ·2026-11-03 ·Jens Breitung, Timo Gervens, Martin Grohe
theoryhot direction similarity 0.57
Abstract · v2: fixed typos and broken link to Lean repository

A natural way to compare two graphs is to align their vertex sets by a bijection and to measure the difference of the aligned adjacency matrices in a matrix norm. Depending on the norm, this yields, for example, the edit distance, the cut distance, the spectral distance, and the local edit distance. To make these distances applicable to graphs of different order, one can consider blowups of the graphs or, equivalently, relax bijections to fractional alignments, that is, optimal transport plans between the uniform distributions on the vertex sets, in the spirit of Gromov-Wasserstein distances. We investigate how much the optimal transport versions can differ from their bijective counterparts, that is, we quantify their integrality gaps. For the edit distance, we improve the best known upper bound on the integrality gap from 3 to 2 and the lower bound from 6/5 to 4/3. For the cut distance, we approach Lovász's conjecture that $δ_\square \le 2δ_\square^{\rm OT}$ from both sides. We improve the previously best known upper bound $δ_\square \le 32 \cdot (δ_\square^{\rm OT})^{1/67}$ (Borgs, Chayes, Lovász, Sós and Vesztergombi, Adv. Math. 2008) to $δ_\square \le C_\varepsilon \cdot (δ_\square^{\rm OT})^{1-\varepsilon}$ for every $\varepsilon > 0$, and we construct graphs $G,H$ with $δ_\square(G,H) = 2δ_\square^{\rm OT}(G,H)$, establishing a factor-2 lower bound that matches Lovász's conjecture. For the local edit and spectral distances, we obtain upper bounds of order $\sqrt{t\ln(1/t)}$ and $\sqrt{t}$, respectively, where $t$ is the corresponding optimal transport distance, and we show that, unlike for the edit and cut distances, no linear upper bounds are possible. Finally, we show that computing the optimal transport distances is NP-hard, and we give hardness of approximation results for the cut, spectral, and local edit distances.

0.25

Separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$

cs.CC cs.DS ·2026-10-28 ·Ijay Narang
similarity 0.56
Abstract

We give complexity-theoretic separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$. Given a graph $G$, and a fugacity $λ>0$, the hard-core model is given by $Z_G(λ)=\sum_{I\in\mathcal I(G)}λ^{|I|}$, where $\mathcal I(G)$ denotes the independent sets of $G$. For $F\ge1$, an $F$-factor approximation to $Z_G(λ)$ is an estimate $\widehat Z$ satisfying $F^{-1}Z_G(λ)\le\widehat Z\le FZ_G(λ)$. Let $\mathcal G_Δ$ denote the class of $Δ$-regular graphs and $\mathcal G_{Δ,Δ}$ the class of $Δ$-regular bipartite graphs. We give two separation results. (1) There exist an integer $Δ\ge3$, a sufficiently large fugacity $λ$, and a constant $c>0$ so that the following hold: (a) For every $δ\in(0,1)$, deterministic $(1+δ)$-factor approximation on $\mathcal G_{Δ,Δ}$ is possible in time $\exp(cn)\operatorname{poly}(n,1/δ)$. (b) Under the Gap-Exponential Time Hypothesis, there exists no deterministic algorithm running in time $\exp(2cn)\operatorname{poly}(n)$ on $\mathcal G_Δ$ that gives an $\frac{11}{10}$-factor approximation. (2) For every fixed $Δ\ge3$ and $\varepsilon\in(0,1)$, for all sufficiently large fugacities $λ$, the following hold: (a) There exists an algorithm which outputs a deterministic $(1+\varepsilon)^n$-factor approximation to $Z_G(λ)$ on $\mathcal G_{Δ,Δ}$ in polynomial time. (b) Under the assumption $\mathrm P\ne\mathrm{NP}$, there exists no deterministic polynomial-time algorithm on $\mathcal G_Δ$ that gives a $(1+\varepsilon)^n$-factor approximation. Both our algorithmic results follow from a new spanning-tree encoding of independent sets that enables an efficient representation of large independent sets.

0.27

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

Cluster-Graph Edit Distance: Optimal Explicit Embeddings, Metric Proxies, and Complexity

cs.DS cs.CCmath.COmath.MG ·2026-08-18 ·JiYe Liu, Wenkai Wang, Qiang Tian, Wenjun Wang
theory similarity 0.56
Abstract · 49 pages, 6 figures. v2: the critical inverse-energy conjecture of v1 is now proved, as a scale-free inverse theorem on the full cone of clo…

The cluster graphs on $n$ vertices, the disjoint unions of complete graphs, have the integer partitions of $n$ as their isomorphism classes, and the quotient edit distance $q^*(λ,μ)=\min_{σ\in S_n}|E(G_λ)\triangleσE(G_μ)|$ makes that set a metric space. Its geometry and its complexity both issue from one identity: $q^*$ is an affine function of the maximum of $\lVert X\rVert_F^2$ over the contingency tables with margins $λ$ and $μ$. Our main result is an explicit optimal embedding. The weighted dyadic sums of the Ferrers staircase, taken at the critical exponent $\frac14$, give a map $F_n$ into $\ell_2^{\,<4n}$ that acts on a single partition and is computable in $O(n)$ time, and its distortion is $Θ(n^{1/4})$. That order is optimal, since $c_2(\mathcal K_n)=Θ(n^{1/4})$: the lower half follows from a $Θ(\sqrt n)$-dimensional Hamming cube of partitions and Enflo's theorem, so the determination needs no other external input. The analytic core is a scale-free inverse inequality for every integer sequence with $v(1)=v(N+1)=0$ and $v(s)-v(s+1)\in s\mathbb Z$: its critical dyadic energy is at least $\lVert v\rVert_1^2/(63504\sqrt{\mathrm{TV}(v)})$. Combinatorially the same identity yields two explicit $\ell_1$ models, the vertex-mass metric on sorted degree sequences with $\frac12δ_1\le q^*<\frac32δ_1$ and the block-energy metric with $q^*\le B\le2q^*-1$, both constants optimal; hence $c_1(\mathcal K_n)\le2$, and an $O(n\log n)$-time algorithm returns an alignment of cost below $2q^*$ carrying the certificate $q^*\in[\lceil(B+1)/2\rceil,B]$. Computationally, deciding $q^*(λ,μ)\le Q$ is strongly NP-complete and admits no FPTAS, while the farthest alignment is polynomial-time solvable. The best constant in the inverse inequality remains open; an exactly solvable chirp family caps it at $\frac23$.

0.12

Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts

cs.DS cs.DC ·2026-11-01 ·Saeed Amiri, Sebastian Siebertz, Wojciech Wawrzyniak
theory similarity 0.55
Abstract

We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts the same $O(\log n)$-bit message to all its neighbors. The framework combines two independent tools. The first is a solver that computes a $(1+δ)$-approximate solution of any local covering linear program with bounded positive integer costs on every class that excludes a fixed minor. The second is a rounding principle: a rounding rule that saves a fixed fraction of its own output, for every feasible input, pays for a solver error fixed in advance, so that an approximate fractional solution yields an exact coefficient. For ordinary domination, we achieve a $2a+1$ approximation against the fractional optimum $γ_f(G)$ for every fixed rational $a\ge1$, whenever every minor has a ratio of edges to vertices of at most $a$. On planar graphs this is seven, matching the lower bound of Hilke, Lenzen, and Suomela. The coefficients are also optimal at bounded treewidth and pathwidth, for $K_t$-minor-free graphs with $3\le t\le9$, on triangle-free planar graphs (five), and on planar graphs of large girth, where it approaches the optimal three. On every fixed surface the exact bound is $7γ(G)$, and we show that a bound of $7γ_f(G)$ is impossible on some fixed surfaces even sequentially. For total domination, on graphs without isolated vertices and under the same minor-density assumption, the exact coefficient is $2a$ against the fractional optimum, including the optimal six on planar graphs. Red-blue domination, and hence set cover and hitting set on planar incidence graphs, has the optimal limiting coefficient four. Our method also gives randomized constant-round and deterministic $O(\log^* n)$-round $(1+\varepsilon)$-approximation schemes, with the randomized cost guarantee holding in expectation.

0.45