关于着色，切割和结构参数化

作者：Ivan Bliznets,Danil Sagunov

摘要：我们研究最大快乐顶点和最大快乐边缘问题。 前一个问题是聚类的变体，其中一些顶点已经分配给了聚类。 第二个问题给出了Multiway Uncut的自然概括，它是经典Multiway 切割问题的补充。 由于它们在理论和实践中的基础性作用，聚类和切割问题一直引起很多关注。 我们通过在Maximum Happy Vertices和Node Multiway Cut之间提供减少来建立这两类问题之间的新联系。 此外，我们研究了最大快乐顶点和最大快乐边缘的平凡参数化的结构和距离。 在这些方向上获得的结果回答了四个作品中明确提出的问题：Agrawal '17，Aravind等。 '16，Choudhari和Reddy '18，Misra和Reddy '17。

原文标题：On Happy Colorings, Cuts, and Structural Parameterizations

原文摘要：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.

地址：https://arxiv.org/abs/1907.06172