AI & ML
Almost Optimal Constant-Round Approximation of Dominating Set in Graph Classes with Excluded Minors
arXiv cs.DC0 views
arXiv:2610.09618v1 Announce Type: cross Abstract: For every fixed proper minor-closed class $\mathscr C$ and every $\epsilon>0$, we give a deterministic LOCAL algorithm that returns a dominating set of size at most $(2a(\mathscr C)+1+\epsilon)\gamma_f(G)$ on every $G\in\mathscr C$. Here $a(\mathscr C)$ is the supremum edge-to-vertex ratio in~$\mathscr C$, and $\gamma_f(G)$ is the fractional domination number. The class also admits a deterministic $(1+\epsilon)$-approximation for fractional dominating set and a randomized algorithm that always returns a dominating set and has expected size at most $(1+\epsilon)\gamma(G)$. In each case, the number of rounds depends only on $\mathscr C$ and~$\epsilon$. 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+\epsilon)\gamma_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~\mbox{$r\ge1$}, no deterministic constant-round LOCAL algorithm achieves an approximation ratio below~\mbox{$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$.
Source:https://arxiv.org/abs/2610.09618PreviousDifferential Refresh Policies for Models Trained on Lagging Data Snapshots: From a Single-Age Equivalence Limit to an Optimal Per-Segment AllocationNextAeroEval: Staged Program and Execution Validation for AI-Generated Drone Missions
Related posts
Best Dyson Vacuum Deals (2026): Dyson Spot+Scrub Ai, Dyson V16 Piston Animal
0Wired
CPU, GPU, TPU, NPU: Who Will Power the Future of Computing?
0dev.to

Lower loss, worse stories: small NCMs trained on TinyStories
0dev.to

I Built LLM Explained: 43 Interactive Pages That Take You From Tokens to AI Agents
0dev.to OpenSource
MIT CSAIL: Astra edita 0,016% de pesos de Qwen3.5-0.8B y sube MATH-500 a 48,1%
0dev.to Programming

Gemma 4 in Rust on TorchTPU: A Native TPU Rig With PyO3 and MCP
0dev.to Rust