Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Drawing Planar Graphs Read chapter Read first chapter

2020 | OriginalPaper | Chapter

Parameterized Algorithms for the Happy Set Problem

Authors : Yuichi Asahiro, Hiroshi Eto, Tesshu Hanaka, Guohui Lin, Eiji Miyano, Ippei Terabaru

Published in: WALCOM: Algorithms and Computation

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

In this paper we introduce the Maximum Happy Set problem (MaxHS) and study its parameterized complexity: For an undirected graph \(G = (V, E)\) and a subset \(S\subseteq V\) of vertices, a vertex v is happy if v and all its neighbors are in S; and otherwise unhappy. Given an undirected graph \(G = (V, E)\) and an integer k, the goal of MaxHS is to find a subset \(S\subseteq V\) of k vertices such that the number of happy vertices is maximized. In this paper we first show that MaxHS is W[1]-hard when parameterized by k. Then, we prove the fixed-parameter tractability of MaxHS when parameterized by the tree-width, the clique-width and k, the neighborhood diversity, or the twin-cover number.

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 Faster Privacy-Preserving Computation of Edit Distance with Moves
next chapter An Experimental Study of a 1-Planarity Testing and Embedding Algorithm
Literature
1.
Agrawal, A.: On the parameterized complexity of happy vertex coloring. IWOCA 2017, 103–115 (2017)MATH
2.
Aravind, N., Kalyanasundaram, S., Kare, A.: Linear time algorithms for happy vertex coloring problems for trees. IWOCA 2016, 281–292 (2016)MathSciNetMATH
3.
Aravind, N., Kalyanasundaram, S., Kare, A., Lauri, J.: Algorithms and hardness results for happy coloring problems. arXiv preprint arXiv:​1705.​08282 (2017)
4.
Asahiro, Y., Hassin, R., Iwama, K.: Complexity of finding dense subgraphs. Discrete Appl. Math. 121, 15–26 (2002)MathSciNetCrossRef
5.
6.
Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238–255 (1995)MathSciNetCrossRef
7.
Bourgeois, N., Giannakos, A., Lucarelli, G., Milis, I., Paschos, V.: Exact and approximation algorithms for densest \(k\)-subgraph. WALCOM 2013, 114–125 (2013)MathSciNetMATH
8.
Broersma, H., Golovach, P., Patel, V.: Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. Theor. Comput. Sci. 485, 69–84 (2013)MathSciNetCrossRef
9.
Bruglieri, M., Ehrgott, M., Hamacher, H., Maffioli, F.: An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints. Discrete Appl. Math. 154(9), 1344–1357 (2006)MathSciNetCrossRef
10.
Cai, L.: Parameterized complexity of cardinality constrained optimization problems. Comput. J. 51, 102–121 (2007)CrossRef
11.
Choudhari, J., Reddy, I.: On structual parameterizations of happy coloring, empire coloring and boxicity. WALCOM 2018, 228–239 (2018)MATH
12.
13.
Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1), 77–114 (2000)MathSciNetCrossRef
14.
15.
Easley, D., Kleinberg, J.: Networks Crowds and Markets: Reasoning about a Highly Connected World. Cambridge University Press, Cambridge (2010)CrossRef
16.
17.
Ganian, R.: Improving vertex cover as a graph parameter. Discrete Math. Theor. Comput. Sci. 17(2), 77–100 (2015)MathSciNetMATH
18.
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)MATH
19.
Keil, J., Brecht, T.: The complexity of clustering in planar graphs. J. Comb. Math. Comb. Comput. 9, 155–159 (1991)MathSciNetMATH
20.
Kortsarz, G., Peleg, D.: On choosing a dense subgraph. FOCS 1993, 692–701 (1993)
21.
22.
Lewis, R., Thiruvady, D., Morgan, K.: Finding happiness: an analysis of the maximum happy vertices problem. Comput. Oper. Res. 103, 265–276 (2019)MathSciNetCrossRef
23.
Misra, N., Reddy, I.: The parameterized complexity of happy colorings. IWOCA 2017, 142–153 (2017)MATH
24.
Zhang, P., Jiang, T., Li, A.: Improved approximation algorithms for the maximum happy vertices and edges problems. COCOON 2015, 159–170 (2015)MathSciNetMATH
25.
26.
Zhang, P., Xu, Y., Jiang, T., Li, A., Lin, G., Miyano, E.: Improved approximation algorithms for the maximum happy vertices and edges problems. Algorithmica 80(5), 1412–1438 (2018)MathSciNetCrossRef
Metadata
Title
Parameterized Algorithms for the Happy Set Problem
Authors
Yuichi Asahiro
Hiroshi Eto
Tesshu Hanaka
Guohui Lin
Eiji Miyano
Ippei Terabaru
Copyright Year
2020
Book
WALCOM: Algorithms and Computation

Print ISBN: 978-3-030-39880-4

Electronic ISBN: 978-3-030-39881-1

Copyright Year: 2020

DOI
https://doi.org/10.1007/978-3-030-39881-1_27

Premium Partner

    Image Credits