On the complexity of the vector connectivity problem

DOI10.1016/J.TCS.2015.04.032MaRDI QIDQ2354404zbMATH OpenOpenAlexFDO

Authors Ferdinando Cicalese, Martin Milanič, Romeo Rizzi

Publication date 13 July 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.2559

zbMATH Keywords

APX-hardnessblock graphsNP-hardnesspolynomial-time algorithmvector connectivity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph $G$ with a requirement $r(v)$ for each vertex $v$, VecCon asks for a minimum cardinality set $S$ of vertices such that every vertex $vinVsetminusS$ is connected to $S$ via $r(v)$ disjoint paths. In the paper introducing the problem, Boros et al. [Networks, 2014] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on $n$-vertex graphs to within a factor of $logn+2$, leaving open the question of whether the problem is NP-hard on general graphs. We show that VecCon is APX-hard in general graphs, and NP-hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs.

Recommendations

• Vector connectivity in graphs
• Vector connectivity in graphs
• On kernelization and approximation for the vector connectivity problem
• On kernelization and approximation for the vector connectivity problem
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs

Cites work

• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Automata, Languages and Programming
• Combinatorial model and bounds for target set selection
• Constant thresholds can make target set selection tractable
• Face covers and the genus problem for apex graphs
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 637286 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Latency-bounded target set selection in social networks
• Network Flow and Testing Graph Connectivity
• On Dominating Sets and Independent Sets of Graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs
• On the approximability of positive influence dominating set in social networks
• Some APX-completeness results for cubic graphs
• Vector connectivity in graphs

Cited in

(6)

• On kernelization and approximation for the vector connectivity problem
• On the complexity landscape of connected \(f\)-factor problems
• scientific article; zbMATH DE number 3984929 (Why is no real title available?)
• Vector connectivity in graphs
• On kernelization and approximation for the vector connectivity problem
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: On the complexity of the vector connectivity problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2354404)