It is proved that, unless SETH fails, for any $\varepsilon, \delta>0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)-approximation of the degeneracy of $G$ with initialization time and amortized update time.
Abstract
In this work, we consider the problem of maintaining an approximate value of degeneracy of a given dynamic $n$-vertex graph $G$ updated by edge insertions and deletions. From the work of Christiansen and Rotenberg [ICALP 2022], it follows that one can design a dynamic data structure for this problem with worst-case update time $\text{poly}(d_{\mathrm{max}}, \log n)$ that maintains an integer between $d$ and $2d+3$ where $d$ is the degeneracy of $G$, under the assumption that $d$ never exceeds $d_{\mathrm{max}}$. We complement their result by providing a conditional lower bound: we prove that, unless SETH fails, for any $\varepsilon, \delta>0$, $k \in \mathbb{N}$, and function $f\colon \mathbb{N}\to \mathbb{N}$, there is no data structure which maintains a $(2-\varepsilon)$-approximation of the degeneracy of $G$ with initialization time $f(d_{\mathrm{max}})\cdot n^k$ and amortized update time $f(d_{\mathrm{max}})\cdot n^{1-\delta}$.
This paper studies fundamental graph optimization problems under differential privacy (DP) and shows new, reconstruction-based lower bounds for large families of sparse graphs with expansion properties and extends lower bounds of Deng et al. (ICLR~'25) to general graphs and to approximate DP.
Jacob Imola, Rasmus Pagh, Lukas Retschmeier· 1 citation
We give a deterministic $(8+\varepsilon)$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\varepsilon>0$. This improves the previous ratio $11+\varepsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is on...
We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|\Gamma|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(\Gamma)\le k \quad\t...
A longstanding fundamental problem of Burr, Erd\H{o}s, Faudree, Rousseau and Schelp (\emph{Trans. Amer. Math. Soc.}, 1982) is to determine the exact value of the least integer $f(m)$, for odd $m\ge3$, such that every tree $T_n$ on $n\ge f(m)$ vertices satisfies $R(T_n,C_m)=2n-1$. We settle this problem for all sufficie...
We prove that there is an absolute positive constant $c$ such that every bipartite graph with $N$ vertices in each part and at least $N^2/2$ edges contains a complete bipartite graph $K_{t,t}$ whenever $N\ge c\, 2^{t}$. This improves the classical K\H{o}v\'ari-S\'os-Tur\'an bound requiring $N$ of order $t\,2^t $. As a...
Dorbec et al. [SIAM J. Discrete Math., 27 (2013)] conjectured that, for all integers $k\geq1$ and $r\geq3$, every connected $r$-regular graph $G$ of order $n$, other than $K_{r,r}$, satisfies $\gamma_{P,k}(G)\leq n/(r+1)$. After disproving this conjecture, Chen et al.[Graphs Combin., 38 (2022)] proposed a corresponding...
Hang Chen, Chang-Hong Lu, Qing-Jie Ye· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
