TY - GEN
T1 - Vector connectivity in graphs
AU - Boros, Endre
AU - Heggernes, Pinar
AU - Van T'Hof, Pim
AU - Milanić, Martin
N1 - Funding Information:
This work is supported by the Research Council of Norway (197548/F20) and by the Slovenian Research Agency (research program P1–0285 and research projects J1–4010, J1–4021, BI-US/12–13–029 and N1–0011: GReGAS, supported in part by the European Science Foundation).
PY - 2013
Y1 - 2013
N2 - Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the VECTOR DOMINATIVITY problem. This problem takes as input a graph G and an integer kυ for every vertex υ of G, and the objective is to find a vertex subset S of minimum cardinality such that every vertex ε either belongs to S, or is connected to at least kε vertices of S by disjoint paths. If we require each path to be of length exactly 1, we get the well-known VECTOR DOMINATION problem, which is a generalization of the famous DOMINATION SET problem and several of its variants. Consequently, our problem becomes NP-hard if an upper bound on the length of the disjoint paths is also supplied as input. Due to the hardness of these domination variants even on restricted graph classes, like split graphs, VECTOR DOMINATIVITY seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that VECTOR DOMINATIVITY can actually be solved in polynomial time on split graphs, in addition to cographs and trees. We also show that the problem can be approximated in polynomial time within a factor of lnn + 2 on all graphs.
AB - Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the VECTOR DOMINATIVITY problem. This problem takes as input a graph G and an integer kυ for every vertex υ of G, and the objective is to find a vertex subset S of minimum cardinality such that every vertex ε either belongs to S, or is connected to at least kε vertices of S by disjoint paths. If we require each path to be of length exactly 1, we get the well-known VECTOR DOMINATION problem, which is a generalization of the famous DOMINATION SET problem and several of its variants. Consequently, our problem becomes NP-hard if an upper bound on the length of the disjoint paths is also supplied as input. Due to the hardness of these domination variants even on restricted graph classes, like split graphs, VECTOR DOMINATIVITY seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that VECTOR DOMINATIVITY can actually be solved in polynomial time on split graphs, in addition to cographs and trees. We also show that the problem can be approximated in polynomial time within a factor of lnn + 2 on all graphs.
UR - http://www.scopus.com/inward/record.url?scp=84893439186&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893439186&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38236-9_30
DO - 10.1007/978-3-642-38236-9_30
M3 - Conference contribution
AN - SCOPUS:84893439186
SN - 9783642382352
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 331
EP - 342
BT - Theory and Applications of Models of Computation - 10th International Conference, TAMC 2013, Proceedings
PB - Springer Verlag
T2 - 10th International Conference on Theory and Applications of Models of Computation, TAMC 2013
Y2 - 20 May 2013 through 22 May 2013
ER -