×

Vector connectivity in graphs. (English) Zbl 1386.05096

Summary: Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the vector connectivity problem. This problem takes as input a graph \(G\) and an integer \(k_v\) for every vertex \(v\) of \(G\), and the objective is to find a vertex subset \(S\) of minimum cardinality such that every vertex \(v\) either belongs to \(S\), or is connected to at least \(k_v\) 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 dominating 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 connectivity seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that vector connectivity 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 \(\ln\,n+2\) on all \(n\)-vertex graphs.

MSC:

05C40 Connectivity
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI

References:

[1] E.Boros, P.Heggernes, P.van’t Hof, and M.Milanič, Vector connectivity in graphs, Proc 10th Ann Conf Theory App Models Comput, Lecture Notes in Computer Science, Vol. 7876, Springer, 2013, pp. 331-342. · Zbl 1372.68119
[2] N.Chen, On the approximability of influence in social networks, SIAM J Discr Math23 (2009), 1400-1415. · Zbl 1203.68314
[3] M.Chlebík and J.Chlebíkova, Approximation hardness of dominating set problems in bounded degree graphs, Inform Comput206 (2008), 1264-1275. · Zbl 1169.68037
[4] F.Cicalese, M.Milanič, and U.Vaccaro, On the approximability and exact algorithms for vector domination and related problems in graphs, Discr Appl Math161 (2013), 750-767. · Zbl 1262.05116
[5] D. G.Corneil, H.Lerchs, and L.Stewart Burlingham, Complement reducible graphs, Discr Appl Math3 (1981), 163-174. · Zbl 0463.05057
[6] D. G.Corneil, Y.Perl, and L.K.Stewart, A linear recognition algorithm for cographs, SIAM J Comput14 (1985), 926-934. · Zbl 0575.68065
[7] M. R.Garey and D. S.Johnson, Computers and intractability, W.H. Freeman and Co., New York, 1979. · Zbl 0411.68039
[8] M. C.Golumbic, Algorithmic graph theory and perfect graphs, 2nd edition, Annals of Discrete Mathematics, Vol. 57, Elsevier, 2004. · Zbl 1050.05002
[9] M.Habib and C.Paul, A simple linear time algorithm for cograph recognition, Discr Appl Math145 (2005), 183-197. · Zbl 1055.05107
[10] P. L.Hammer, B.Simeone, The splittance of a graph Combinatorica1 (1981), 275-284. · Zbl 0492.05043
[11] J.Harant, A.Prochnewski, and M.Voigt, On dominating sets and independent sets of graphs, Combin Probab Comput8 (1999), 547-553. · Zbl 0959.05080
[12] T. W.Haynes, S. T.Hedetniemi, and P. J.Slater, Fundamentals of domination in graphs, Dekker, New York, 1998. · Zbl 0890.05002
[13] T. W.Haynes, S. T.Hedetniemi and P. J.Slater, Domination in graphs: Advanced topics, Marcel Dekker, New York, 1998. · Zbl 0883.00011
[14] D.Kempe, J.Kleinberg, and E.Tardos, Maximizing the spread of influence through a social network, Proc 9th ACM SIGKDD Int Conf Knowl Discov Data Mining, ACM Press, 2003, pp. 137-146.
[15] N.Mahadev and U.Peled, Threshold graphs and related topics, Annals Disc Mathematics, Vol. 56, North Holland, 1995. · Zbl 0852.05001
[16] A.Nichterlein, R.Niedermeier, J.Uhlmann and M.Weller, On tractable cases of Target Set Selection, Soc Netw Anal Mining3 (2013), 233-256.
[17] J.Oxley, Matroid theory, Oxford University Press, Oxford, 1992. · Zbl 0784.05002
[18] H.Perfect, Applications of Menger’s graph theorem, J Math Anal Appl22 (1968), 96-111. · Zbl 0157.55301
[19] J. S.Pym, A proof of the linkage theorem, J Math Anal Appl27 (1969), 636-638. · Zbl 0184.27802
[20] A.Schrijver, Combinatorial optimization, Polyhedra and efficiency, Vol. A-C. Algorithms and Combinatorics, Vol. 24, Springer‐Verlag, Berlin, 2003. · Zbl 1041.90001
[21] D.J.A.Welsh, Matroid theory, L.M.S. Monographs, Vol. 8, Academic Press, London‐New York, 1976. · Zbl 0343.05002
[22] L. A.Wolsey, An analysis of the greedy algorithm for the submodular set covering problem, Combinatorica2 (1982), 385-393. · Zbl 0508.68021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.