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 v∈VS is connected to S via r(v) disjoint paths. In the paper introducing the problem, Boros et al. [4] 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 log n + 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.

On the complexity of the vector connectivity problem

Cicalese, Ferdinando;RIZZI, ROMEO
2015-01-01

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 v∈VS is connected to S via r(v) disjoint paths. In the paper introducing the problem, Boros et al. [4] 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 log n + 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.
2015
APX-hardness; Block graphs; NP-hardness; Polynomial-time algorithm; Vector connectivity
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/933103
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact