Top

Published in:

2019 | OriginalPaper | Chapter

On Happy Colorings, Cuts, and Structural Parameterizations

Authors : Ivan Bliznets, Danil Sagunov

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

We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters. The second problem gives a natural generalization of Multiway Uncut, which is the complement of the classical Multiway Cut problem. Due to their fundamental role in theory and practice, clusterization and cut problems has always attracted a lot of attention. We establish a new connection between these two classes of problems by providing a reduction between Maximum Happy Vertices and Node Multiway Cut. Moreover, we study structural and distance to triviality parameterizations of Maximum Happy Vertices and Maximum Happy Edges. Obtained results in these directions answer questions explicitly asked in four works: Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17.

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 Graph Functionality

next chapter Shortest Reconfiguration of Matchings

Agrawal, A.: On the parameterized complexity of happy vertex coloring. In: Brankovic, L., Ryan, J., Smyth, W.F. (eds.) IWOCA 2017. LNCS, vol. 10765, pp. 103–115. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78825-8_9CrossRef

Aravind, N.R., Kalyanasundaram, S., Kare, A.S.: Linear time algorithms for happy vertex coloring problems for trees. In: Mäkinen, V., Puglisi, S.J., Salmela, L. (eds.) IWOCA 2016. LNCS, vol. 9843, pp. 281–292. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44543-4_22CrossRefMATH

Aravind, N., Kalyanasundaram, S., Kare, A.S., Lauri, J.: Algorithms and hardness results for happy coloring problems. arXiv preprint arXiv:1705.08282 (2017)

Belmonte, R., Golovach, P.A., van ’t Hof, P., Paulusma, D.: Parameterized complexity of two edge contraction problems with degree constraints. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 16–27. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03898-8_3CrossRefMATH

Boral, A., Cygan, M., Kociumaka, T., Pilipczuk, M.: A fast branching algorithm for cluster vertex deletion. Theory Comput. Syst. 58(2), 357–376 (2015)MathSciNetCrossRef

Chitnis, R., Fomin, F.V., Lokshtanov, D., Misra, P., Ramanujan, M.S., Saurabh, S.: Faster exact algorithms for some terminal set problems. In: Gutin, G., Szeider, S. (eds.) IPEC 2013. LNCS, vol. 8246, pp. 150–162. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03898-8_14CrossRefMATH

Choudhari, J., Reddy, I.V.: On structural parameterizations of happy coloring, empire coloring and boxicity. In: Rahman, M.S., Sung, W.-K., Uehara, R. (eds.) WALCOM 2018. LNCS, vol. 10755, pp. 228–239. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-75172-6_20CrossRefMATH

Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825–847 (2005)MathSciNetCrossRef

Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1–3), 77–114 (2000)MathSciNetCrossRef

10.

Cygan, M., et al.: Parameterized Algorithms, vol. 3. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-319-21275-3CrossRefMATH

11.

Cygan, M., Philip, G., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Dominating set is fixed parameter tractable in claw-free graphs. Theor. Comput. Sci. 412(50), 6982–7000 (2011). https://doi.org/10.1016/j.tcs.2011.09.010MathSciNetCrossRefMATH

12.

Diestel, R.: Graph Theory. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-53622-3CrossRefMATH

13.

Gao, H., Gao, W.: Kernelization for maximum happy vertices problem. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018. LNCS, vol. 10807, pp. 504–514. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-77404-6_37CrossRef

14.

Hlineny, P., Oum, S.I., Seese, D., Gottlob, G.: Width parameters beyond tree-width and their applications. Comput. J. 51(3), 326–362 (2007)CrossRef

15.

Hüffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory Comput. Syst. 47(1), 196–217 (2008)MathSciNetCrossRef

16.

Jansen, K., Scheffler, P., Woeginger, G.: The disjoint cliques problem. RAIRO-Oper. Res. 31(1), 45–66 (1997)MathSciNetCrossRef

17.

Lackner, M., Pichler, R., Rümmele, S., Woltran, S.: Multicut on graphs of bounded clique-width. In: Lin, G. (ed.) COCOA 2012. LNCS, vol. 7402, pp. 115–126. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31770-5_11CrossRef

18.

Lewis, R., Thiruvady, D., Morgan, K.: Finding happiness: an analysis of the maximum happy vertices problem. Comput. Oper. Res. 103, 265–276 (2019)MathSciNetCrossRef

19.

Misra, N., Reddy, I.V.: The parameterized complexity of happy colorings. In: Brankovic, L., Ryan, J., Smyth, W.F. (eds.) IWOCA 2017. LNCS, vol. 10765, pp. 142–153. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78825-8_12CrossRef

20.

Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, Upper Saddle River (1981)MATH

21.

Todinca, I.: Coloring powers of graphs of bounded clique-width. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol. 2880, pp. 370–382. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39890-5_32CrossRef

22.

Xu, Y., Goebel, R., Lin, G.: Submodular and supermodular multi-labeling, and vertex happiness. CoRR (2016)

23.

Zhang, P., Jiang, T., Li, A.: Improved approximation algorithms for the maximum happy vertices and edges problems. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 159–170. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21398-9_13CrossRef

24.

Zhang, P., Li, A.: Algorithmic aspects of homophyly of networks. Theor. Comput. Sci. 593, 117–131 (2015)MathSciNetCrossRef

25.

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

Title: On Happy Colorings, Cuts, and Structural Parameterizations
Authors: Ivan Bliznets
Danil Sagunov
Publisher: Springer International Publishing
Book: Graph-Theoretic Concepts in Computer Science
Print ISBN: 978-3-030-30785-1

Electronic ISBN: 978-3-030-30786-8

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-30786-8_12

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