Top

Published in:

2017 | OriginalPaper | Chapter

The Parameterized Complexity of the Equidomination Problem

Authors : Oliver Schaudt, Fabian Senger

Published in: Graph-Theoretic Concepts in Computer Science

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A graph \(G=(V,E)\) is called equidominating if there exists a value

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-68705-6_31/437967_1_En_31_IEq2_HTML.gif

and a weight function

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-68705-6_31/437967_1_En_31_IEq3_HTML.gif

such that the total weight of a subset \(D\subseteq V\) is equal to t if and only if D is a minimal dominating set. To decide whether or not a given graph is equidominating is referred to as the Equidomination problem.

In this paper we show that two parameterized versions of the Equidomination problem are fixed-parameter tractable: the first parameterization considers the target value t leading to the Target-t Equidomination problem. The second parameterization allows only weights up to a value k, which yields the k-Equidomination problem.

In addition, we characterize the graphs whose every induced subgraph is equidominating. We give a finite forbidden induced subgraph characterization and derive a fast recognition algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter New Results on Weighted Independent Domination

next chapter Homothetic Triangle Contact Representations

http://arxiv.org/abs/1705.05599.

Benzaken, C., Hammer, P.: Linear separation of dominating sets in graphs. In: Bollobs, B. (ed.) Advances in Graph Theory, Annals of Discrete Mathematics, vol. 3, pp. 1–10. Elsevier (1978), http://www.sciencedirect.com/science/article/pii/S0167506008704928

Brandstädt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 267–277. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35261-4_30 CrossRef

Cournier, A., Habib, M.: A new linear algorithm for modular decomposition. In: Tison, S. (ed.) CAAP 1994. LNCS, vol. 787, pp. 68–84. Springer, Heidelberg (1994). https://doi.org/10.1007/BFb0017474 CrossRef

Finbow, A., Hartnell, B., Nowakowski, R.: Well-dominated graphs: a collection of well-covered ones. Ars Combin. 25, 5–10 (1988)MathSciNetMATH

Gutin, G., Zverovich, V.E.: Upper domination and upper irredundance perfect graphs. Discrete Math. 190(1), 95–105 (1998). http://www.sciencedirect.com/science/article/pii/S0012365X98000363

Kim, E.J., Milanič, M., Schaudt, O.: Recognizing k-equistable graphs in FPT time. In: Mayr, E.W. (ed.) WG 2015. LNCS, vol. 9224, pp. 487–498. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53174-7_34 CrossRef

Levit, V.E., Milanič, M., Tankus, D.: On the recognition of k-equistable graphs. In: Golumbic, M.C., Stern, M., Levy, A., Morgenstern, G. (eds.) WG 2012. LNCS, vol. 7551, pp. 286–296. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34611-8_29 CrossRef

McConnell, R.M., Spinrad, J.P.: Modular decomposition and transitive orientation. Discrete Math. 201(13), 189–241 (1999). http://www.sciencedirect.com/science/article/pii/S0012365X98003197

Milanič, M., Orlin, J., Rudolf, G.: Complexity results for equistable graphs and related classes. Ann. Oper. Res. 188, 359–370 (2011). https://doi.org/10.1007/s10479-010-0720-3 CrossRefMathSciNetMATH

10.

Payan, C.: A class of threshold and domishold graphs: equistable and equidominating graphs. Discrete Math. 29(1), 47–52 (1980). https://doi.org/10.1016/0012-365X(90)90286-Q CrossRefMathSciNetMATH

11.

Rautenbach, D., Zverovich, V.: Perfect graphs of strong domination and independent strong domination. Discrete Math. 226(1), 297–311 (2001). http://www.sciencedirect.com/science/article/pii/S0012365X00001163

12.

Tedder, M., Corneil, D., Habib, M., Paul, C.: Simpler linear-time modular decomposition via recursive factorizing permutations. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 634–645. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70575-8_52 CrossRef

13.

Zverovich, I.E., Zverovich, V.E.: A characterization of domination perfect graphs. J. Graph Theor. 15(2), 109–114 (1991). https://doi.org/10.1002/jgt.3190150202 CrossRefMathSciNetMATH

Title: The Parameterized Complexity of the Equidomination Problem
Authors: Oliver Schaudt
Fabian Senger
Publisher: Springer International Publishing
Book: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-319-68704-9

Electronic ISBN: 978-3-319-68705-6

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-68705-6_31

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner