Vector connectivity in graphs1. Issue 4 (10th February 2014)

• Record Type: Journal Article
• Authors: Boros, Endre; Heggernes, Pinar; van 't Hof, Pim; Milanič, Martin
• Is Part Of: Networks. Volume 63:Issue 4(2014:Jul.)
• Page Start: 277
• Page End: 285
• Publication Date: 2014-02-10
• Subjects: Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21545
• Languages: English
• ISSNs: 0028-3045

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the <sc>VECTOR CONNECTIVITY</sc> problem. This problem takes as input a graph <italic>G</italic> and an integer <italic>k</italic><sub><italic>v</italic></sub> for every vertex <italic>v</italic> of <italic>G</italic>, and the objective is to find a vertex subset <italic>S</italic> of minimum cardinality such that every vertex <italic>v</italic> either belongs to <italic>S</italic>, or is connected to at least <italic>k</italic><sub><italic>v</italic></sub> vertices of <italic>S</italic> by disjoint paths. If we require each path to be of length exactly 1, we get the well‐known <sc>VECTOR DOMINATION</sc> problem, which is a generalization of the famous <sc>DOMINATING SET</sc> 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, <sc>VECTOR CONNECTIVITY</sc> seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that <sc>VECTOR CONNECTIVITY</sc> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pghgzcxq96" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:net21545:net21545-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>ln</mml:mi><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></alternatives> on all <italic>n</italic>‐vertex graphs.Copyright © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 63(4), 277–285 2014</p> </abstract>