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

推荐订阅源

C
Check Point Blog
罗磊的独立博客
量子位
Microsoft Azure Blog
Microsoft Azure Blog
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
J
Java Code Geeks
M
MIT News - Artificial intelligence
月光博客
月光博客
IT之家
IT之家
D
DataBreaches.Net
A
About on SuperTechFans
博客园 - 三生石上(FineUI控件)
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
Last Week in AI
Last Week in AI
D
Docker
The GitHub Blog
The GitHub Blog
B
Blog
V
Visual Studio Blog
博客园 - Franky
N
Netflix TechBlog - Medium
博客园 - 【当耐特】
Martin Fowler
Martin Fowler
博客园 - 聂微东
U
Unit 42

cs.DS updates on arXiv.org

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 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 Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
Minimum Connected Transversals in Graphs: New Hardness Re...
Nina Chiarelli, Tatiana R. Hartinger, Matthew Johnson, Martin Mi · 2017-06-25 · via cs.DS updates on arXiv.org

We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. Just like their original counterparts, these variants are NP-complete for general graphs. A graph $G$ is $H$-free for some graph $H$ if $G$ contains no induced subgraph isomorphic to $H$. It is known that Connected Vertex Cover is NP-complete even for $H$-free graphs if $H$ contains a claw or a cycle. We show that the two other connected variants also remain NP-complete if $H$ contains a cycle or claw. In the remaining case $H$ is a linear forest. We show that Connected Vertex Cover, Connected Feedback Vertex Set, and Connected Odd Cycle Transversal are polynomial-time solvable for $sP_2$-free graphs for every constant $s\geq 1$. For proving these results we use known results on the price of connectivity for vertex cover, feedback vertex set, and odd cycle transversal. This is the first application of the price of connectivity that results in polynomial-time algorithms.