nach oben

Journal of Combinatorial Optimization

Erschienen in:

21.03.2017

The k-hop connected dominating set problem: approximation and hardness

verfasst von: Rafael S. Coelho, Phablo F. S. Moura, Yoshiko Wakabayashi

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (\({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\)). We prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {NP}\)-hard on planar bipartite graphs of maximum degree 4. We also prove that \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) is \(\mathscr {APX}\)-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\) on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for \({\textsc {Min}}k{\hbox {-}\textsc {CDS}}\). Finally, when \(k=1\), we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.

Vorheriger Artikel Approximation for vertex cover in -conflict graphs

Nächster Artikel An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Amiri SA, de Mendez PO, Rabinovich R, Siebertz S (2017) Distributed domination on graph classes of bounded expansion. ArXiv pre-prints arXiv:1702.02848

Arvind K, Regan CP (1992) Connected domination and Steiner set on weighted permutation graphs. Inf Process Lett 41(4):215–220MathSciNetCrossRefMATH

Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation. Springer, BerlinCrossRefMATH

Berry A, Bordat J, Cogis O (1999) Generating all the minimal separators of a graph. Proceedings of the 25th international workshop on graph-theoretic concepts in computer science. Springer, Berlin, pp 167–172CrossRef

Blum J, Ding M, Thaeler A, Cheng X (2005) Connected dominating set in sensor networks and MANETs. In: Du D, Pardalos PM (eds) Handbook of combinatorial optimization. Springer, Berlin, pp 329–369CrossRef

Bondy JA, Murty USR (2008) Graph theory. Graduate texts in mathematics, vol 244. Springer, New York

Bonsma P (2012) Max-leaves spanning tree is APX-hard for cubic graphs. J Discrete Algorithms 12:14–23MathSciNetCrossRefMATH

Bonsma P, Zickfeld F (2008) A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs. In: Graph-Theoretic concepts in computer science. 34th international workshop, WG 2008, Springer, Berlin, pp 66–77 Springer, Berlin

Borradaile G, Le H (2015) Optimal dynamic program for \(r\)-domination problems over tree decompositions. CoRR arXiv:1502.00716

Brandstädt A, Dragan FF (1998) A linear-time algorithm for connected \(r\)-domination and Steiner tree on distance-hereditary graphs. Networks 31(3):177–182MathSciNetCrossRefMATH

Brandstädt A, Le VB, Spinrad JP (1987) Graph classes: a survey. Society for Industrial Mathematics, Philadelphia, Monographs on discrete mathematics and applicationsMATH

Chandran LS, Grandoni F (2006) A linear time algorithm to list the minimal separators of chordal graphs. Discrete Math 306(3):351–358MathSciNetCrossRefMATH

Cheng X, Huang X, Li D, Wu W, Du D (2003) A polynomial-time approximation scheme for the minimum connected dominating set in ad hoc wireless networks. Networks 42:202–208MathSciNetCrossRefMATH

Chlebík M, Chlebíková J (2004) Approximation hardness of dominating set problems. In: European symposium on algorithms. Springer, pp 192–203

Chlebík M, Chlebíková J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inf Comput 206(11):1264–1275MathSciNetCrossRefMATH

Chvátal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233–235MathSciNetCrossRefMATH

Coelho RS, Moura PFS, Wakabayashi Y (2015) The \(k\)-hop connected dominating set problem: hardness and polyhedra. Electron Notes Discrete Math 50:59–64CrossRefMATH

Cohen-Addad V, Colin de Verdière E, Klein PN, Mathieu C, Meierfrankenfeld D (2016) Approximating connectivity domination inweighted bounded-genus graphs. Proceedings of the forty-eighth annual ACM symposium on theory of computing, STOC ’16. ACM, New York, pp 584–597

Colbourn CJ, Stewart LK (1990) Permutation graphs: connected domination and Steiner trees. Discrete Math 86(1):179–189MathSciNetCrossRefMATH

D’Atri A, Moscarini M (1988) Distance-hereditary graphs, Steiner trees, and connected domination. SIAM J Comput 17(3):521–538MathSciNetCrossRefMATH

Demaine ED, Hajiaghayi M (2005) Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA ’05. Society for Industrial and Applied Mathematics, pp 590–601

Dhanalakshmi S, Sadagopan N, Manogna V (2016) On \(2{K}_2\)-free graphs-structural and combinatorial view. ArXiv pre-prints arXiv:1602.03802

Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439–485MathSciNetCrossRefMATH

Dinur I, Guruswami V, Khot S, Regev O (2005) A new multilayered PCP and the hardness of hypergraph vertex cover. SIAM J Comput 34(5):1129–1146MathSciNetCrossRefMATH

Dragan F (1993) HT-graphs: centers, connected \(r\)-domination and Steiner trees. Comput Sci 1(2):64–83MathSciNet

Du D, Wan P (2012) Connected dominating set: theory and applications. Springer, BerlinMATH

Du D, Graham RL, Pardalos PM, Wan P, Wu W, Zhao W (2008) Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of the ACM-SIAM symposium on discrete algorithms, pp 167–175

Dubhashi D, Mei A, Panconesi A, Radhakrishnan J, Srinivasan A (2005) Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J Comput Syst Sci 71(4):467–479MathSciNetCrossRefMATH

Escoffier B, Gourvès L, Monnot J (2010) Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. J Discrete Algorithms 8(1):36–49MathSciNetCrossRefMATH

Fernau H, Manlove DF (2009) Vertex and edge covers with clustering properties: complexity and algorithms. J Discrete Algorithms 7(2):149–167MathSciNetCrossRefMATH

Gao X, Wang W, Zhang Z, Zhu S, Wu W (2010) A PTAS for minimum \(d\)-hop connected dominating set in growth-bounded graphs. Optim Lett 4(3):321–333MathSciNetCrossRefMATH

Golumbic MC (2004) Algorithmic graph theory and perfect graphs, vol 57. Elsevier, AmsterdamMATH

Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387MathSciNetCrossRefMATH

Guha S, Khuller S (1999) Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf Comput 150(1):57–74MathSciNetCrossRefMATH

Gyárfás A (1998) Generalized split graphs and Ramsey numbers. J Comb Theory A 81(2):255–261MathSciNetCrossRefMATH

Haglin DJ, Venkatesan SM (1991) Approximation and intractability results for the maximum cut problem and its variants. IEEE Trans Comput 40(1):110–113MathSciNetCrossRef

Haynes TW, Hedetniemi S, Slater P (1998) Fundamentals of domination in graphs. CRC Press, Boca RatonMATH

Heggernes P, Kratsch D (2007) Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic J Comput 14(1):87–108MathSciNetMATH

Hong-Gwa Y, Chang GJ (1998) Weighted connected domination and Steiner trees in distance-hereditary graphs. Discrete Appl Math 87(1):245–253MathSciNetCrossRefMATH

Jallu RK, Prasad PR, Das GK (2017) Distributed construction of connected dominating set in unit disk graphs. J Parallel Distrib Comput 104:159–166CrossRef

Kanté M, Limouzy V, Mary A (2011) Nourine L. Enumeration of minimal dominating sets and variants Lecture notes in computer science 6914:298–309

Khuller S, Yang S (2016) Revisiting connected dominating sets: an optimal local algorithm. In: Jansen C, Mathieu K, Rolim JDP, Umans C (eds) Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX/RANDOM 2016), Leibniz international proceedings in informatics (LIPIcs), vol 60. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, pp 11:1–11:12

Kloks T, Kratsch D (1998) Listing all minimal separators of a graph. SIAM J Comput 27(3):605–613MathSciNetCrossRefMATH

Liang YD (1995) Steiner set and connected domination in trapezoid graphs. Inf Process Lett 56(2):101–108MathSciNetCrossRef

Lokshtanov D, Misra N, Philip G, Ramanujan MS, Saurabh S (2013) Hardness of \(r\)-dominating set on graphs with diameter \(r + 1\). In: G. Gutin, S. Szeider (eds) Parameterized and exact computation. Lecture notes in computer science, vol 8246. Springer, Berlin, pp 255–267

Moscarini M (1993) Doubly chordal graphs, Steiner trees, and connected domination. Networks 23(1):59–69MathSciNetCrossRefMATH

Müller H, Brandstädt A (1987) The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theor Comput Sci 53(2):257–265MathSciNetCrossRefMATH

Nguyen TN, Huynh DT (2006) Connected \(d\)-hop dominating sets in mobile ad hoc networks. In: Proceedings of the 4th international symposium on modeling and optimization in mobile ad hoc and wireless networks, pp 1–8

Nieberg T, Hurink J (2006) A PTAS for the minimum dominating set problem in unit disk graphs. In: Erlebach T, Persiano G (eds) Approximation and Online Algorithms, WAOA 2005, vol 3879. Lecture Notes in Computer Science. Springer, Berlin, pp 296–306

Nikolopoulos SD, Palios L (2006) Minimal separators in \({P}_4\)-sparse graphs. Discrete Math 306(3):381–392MathSciNetCrossRefMATH

Ramalingam G, Rangan CP (1988) A unified approach to domination problems on interval graphs. Inf Process Lett 27(5):271–274MathSciNetCrossRefMATH

Ren W, Zhao Q (2011) A note on ‘Algorithms for connected set cover problem and fault-tolerant connected set cover problem’. Theor Comput Sci 412(45):6451–6454CrossRefMATH

Ruan L, Du H, Jia X, Wu W, Li Y, Ko K (2004) A greedy approximation for minimum connected dominating sets. Theor Comput Sci 329(1–3):325–330MathSciNetCrossRefMATH

Wan P, Alzoubi KM, Frieder O (2002) Distributed construction of connected dominating set in wireless ad hoc networks. Proceedings of the twenty-first annual joint conference of the IEEE computer and communications societies 3:1597–1604CrossRef

White K, Farber M, Pulleyblank W (1985) Steiner trees, connected domination and strongly chordal graphs. Networks 15(1):109–124MathSciNetCrossRefMATH

Yadav AK, Yadav RS, Singh R, Singh AK (2015) Connected dominating set for wireless ad hoc networks: a survey. Int J Eng Syst Model Simul 7(1):22–34MathSciNet

Yu J, Wang N, Wang G, Yu D (2013) Connected dominating sets in wireless ad hoc and sensor networks–a comprehensive survey. Comput Commun 36(2):121–134CrossRef

Zhang Z, Gao X, Wu W, Du D (2009) A PTAS for minimum connected dominating set in 3-dimensional wireless sensor networks. J Glob Optim 45(3):451–458MathSciNetCrossRefMATH

Titel: The k-hop connected dominating set problem: approximation and hardness
verfasst von: Rafael S. Coelho
Phablo F. S. Moura
Yoshiko Wakabayashi
Publikationsdatum: 21.03.2017
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2017
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-017-0128-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2017

Competitive analysis of bi-directional non-preemptive conversion

Extremal coloring for the anti-Ramsey problem of matchings in complete graphs

Discrete parallel machine makespan ScheLoc problem

2-Distance coloring of planar graphs with girth 5

An FPTAS for generalized absolute 1-center problem in vertex-weighted graphs

Change-making problems revisited: a parameterized point of view