惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

博客园 - 叶小钗
Exploit-DB.com RSS Feed
Exploit-DB.com RSS Feed
MongoDB | Blog
MongoDB | Blog
V
Visual Studio Blog
Security Archives - TechRepublic
Security Archives - TechRepublic
Jina AI
Jina AI
cs.CV updates on arXiv.org
cs.CV updates on arXiv.org
S
Secure Thoughts
Simon Willison's Weblog
Simon Willison's Weblog
博客园_首页
T
Threat Research - Cisco Blogs
Attack and Defense Labs
Attack and Defense Labs
H
Heimdal Security Blog
L
Lohrmann on Cybersecurity
爱范儿
爱范儿
Stack Overflow Blog
Stack Overflow Blog
Last Week in AI
Last Week in AI
T
Troy Hunt's Blog
C
CERT Recently Published Vulnerability Notes
P
Proofpoint News Feed
小众软件
小众软件
Security Latest
Security Latest
F
Fortinet All Blogs
Vercel News
Vercel News
博客园 - 司徒正美
C
Cisco Blogs
T
Tailwind CSS Blog
Recorded Future
Recorded Future
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Latest news
Latest news
V
Vulnerabilities – Threatpost
S
Schneier on Security
Forbes - Security
Forbes - Security
www.infosecurity-magazine.com
www.infosecurity-magazine.com
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
The Last Watchdog
The Last Watchdog
G
GRAHAM CLULEY
D
Darknet – Hacking Tools, Hacker News & Cyber Security
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
Microsoft Azure Blog
Microsoft Azure Blog
Google DeepMind News
Google DeepMind News
The Register - Security
The Register - Security
博客园 - 三生石上(FineUI控件)
O
OpenAI News
F
Full Disclosure
L
LINUX DO - 热门话题
Help Net Security
Help Net Security
H
Hackread – Cybersecurity News, Data Breaches, AI and More
博客园 - Franky

cs.DS updates on arXiv.org

Learning with Simulators: No Regret in a Computationally Bounded World Temporal Conductance and Bounds on the Voter Model for Dynamic Networks Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds A unified complexity bound for logconcave sampling Nearly Instance Optimal Sparse Matrix Approximation from Matrix-Vector Products Near-Optimal Distributed 2-Ruling Sets on Graphs with Low Arboricity On finding exact solutions of linear programs in the oracle model A Fast Gaussian Mechanism under Continual Observation, with Applications Beyond Frequency Marching: Orbit Recovery in Dihedral and Projected Multireference Alignment Density estimation for Hellinger via minimum-distance estimators: mixtures of Gaussians, log-concave, and more A Unified Lower Bound on the Noisy Query Complexity of Boolean Functions The Power of Test-Time Training for Approximate Sampling Fixed-Parameter Tractability of Private Synthetic Data Generation Express Language Modeling The Arithmetic Circuit Combinatorial Nullstellensatz is NP-hard Kikuchi Graphs of Random Hypergraphs are Approximately Johnson Complexity and Algorithms for Unary Translocation Distance From Estimates to Schedules: Learning-Augmented Restricted Assignment Optimal Online Equitable Allocation with Indivisible Resources Minimum Complete MR Subsets under Semantic-Mutation Fault Models: A Support-Set Domination Boundary Revisiting Diameter in Directed Graphs Differentially Private Range Subgraph Counting A note on rounding fractional matchings with constant-factor strong negative correlation Towards Tight Bounds for Streaming Attention Quantum enhanced rare event discovery and sampling Sharp Low-Degree Thresholds for Planted-vs-Planted Testing A General Framework for Dynamic Consistent Submodular Maximization The Preisach Extremum Stack is a Shannon-Minimal Sufficient Statistic for Rate-Independent Functionals HRNN: A Hybrid Graph Index for Approximate Reverse k-Nearest Neighbor Search on High-Dimensional Vectors Parallel Metric Skip Lists and Nearest Neighbor Search From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization On the gap of quiver representations Online K-d tree for approximate neighborhood search in data streams Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs Scalable Concurrent Queues for GPU Towards Optimal Robustness in Learning-Augmented Paging Adversarial Configurations for the ReCom Transition Function On Thin Perfect Matchings up to Polylogarithmic Factors Multiagent Matroid Upgrading: Greedy is Fair and Efficient The anti-lexicographic SUS-anchor: a near-optimal k=1 sampling scheme Dynamic Breadth First Search with Predictions The World's Fastest Matching Engine Algorithm Repeated Descent: A Framework for Online Budget-Feasible Auctions Eulerian-spanning set and coboundary operator: An investigation of maxcut beyond planar graphs Easy, robust approximate message passing for planted spike models High-Dimensional Expanders, the Sparsest Cut Problem, and Steurer's Conjecture Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms An Upper Bound on Grothendieck's Constant Neuro-symbolic Syntactic Parsing: Shaping a Neural Network with the CYK Algorithm Stepsize Hedging: an Alternative Mechanism for Accelerating Gradient Descent Retriever Portfolios: A Principled Approach to Adaptive RAG Tree Containment Parameterized by Scanwidth Incremental BPE Tokenization Listing Even Cycles Faster than the Submodular-Width Barrier Energy-Efficient Aggregation and Minimum-Degree Spanning Trees in Radio Networks On Language Generation in the Limit with Bounded Memory Improved Guarantees for Heterogeneous Treatment-Effect Estimation via Matrix Completion Low-degree estimation thresholds in planted hypergraphs and tensor PCA Selection Hyper-heuristics Can Automatically Adjust the Learning Period to Optimally Solve Pseudo-Boolean Problems TC-MIS: Maximal Independent Set on Tensor-cores Sampling Directed Eulerian Tours in $\widetilde O(m^{3/2})$ Time Explaining Rankings with Hidden Group Bonuses Distributed Gaussian Mean Testing under Communication Constraints: messages, samples, and coins An Improved Greedy Approximation for (Metric) $k$-Means Residual-Entropy Accounting for Routed Atom-Budgeted Learned Indexes Optimal Rates for Differentially Private Hypothesis Testing with E-values A Fresh Look at Lamarckian Evolution and the Baldwin Effect Disjunctive Sum of Squares A Deterministic Separation Lemma Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs Quantum principal component analysis without eigenvector recovery Privately Estimating Monotone Statistics in Polynomial Time Smoothed Score Queries and the Complexity of Sampling Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals Tree Search With Predictions On the Detection of Commutative Factors in Factor Graphs: Necessary and Sufficient Conditions Parsimonious Learning-Augmented Online Metric Matching Where to Split and When to Charge: Optimal Route Construction from Customer Permutations in Electric Vehicle Routing Low Soundness Linearity Testing on the Half-Slice On the Complexity of Bilevel Independent Set Problem Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications CAFS: A Cache-Aware Frequency Sort for Low-Cardinality Integer Data on x86-64 Approximation algorithms for the prize-collecting rural postman problem A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees
The tape reconfiguration problem and its consequences for dominating set reconfiguration
Nicolas Bousquet, Quentin Deschamps, Arnaud Mary, Amer E. Mouawa · 2025-05-02 · via cs.DS updates on arXiv.org

A dominating set of a graph $G=(V,E)$ is a set of vertices $D \subseteq V$ whose closed neighborhood is $V$, i.e., $N[D]=V$. We view a dominating set as a collection of tokens placed on the vertices of $D$. In the token sliding variant of the Dominating Set Reconfiguration problem (TS-DSR), we seek to transform a source dominating set into a target dominating set in $G$ by sliding tokens along edges, and while maintaining a dominating set all along the transformation. TS-DSR is known to be PSPACE-complete even restricted to graphs of pathwidth $w$, for some non-explicit constant $w$ and to be XL-complete parameterized by the size $k$ of the solution. The first contribution of this article consists in using a novel approach to provide the first explicit constant for which the TS-DSR problem is PSPACE-complete, a question that was left open in the literature. From a parameterized complexity perspective, the token jumping variant of DSR, i.e., where tokens can jump to arbitrary vertices, is known to be FPT when parameterized by the size of the dominating sets on nowhere dense classes of graphs. But, in contrast, no non-trivial result was known about TS-DSR. We prove that DSR is actually much harder in the sliding model since it is XL-complete when restricted to bounded pathwidth graphs and even when parameterized by $k$ plus the feedback vertex set number of the graph. This gives, for the first time, a difference of behavior between the complexity under token sliding and token jumping for some problem on graphs of bounded treewidth. All our results are obtained using a brand new method, based on the hardness of the so-called Tape Reconfiguration problem, a problem we believe to be of independent interest.