On the maximum cardinality cut problem in proper interval graphs and related graph classes
Yükleniyor...
Dosyalar
Tarih
2022-01-04
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Elsevier B.V.
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (?,?,?)-clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most ? labels, a) every label consists of at most ? sets of twin vertices, and b) all the labels together induce a graph with independence number at most ?. We show that for every two constants ?,?>0 the problem is FPT when parameterized by ? plus the smallest width of an (?,?,?)-clique-width decomposition.
Açıklama
Anahtar Kelimeler
Bubble model, Bubble models, Cardinalities, Clique-decomposition, Clique decomposition, Clique-width, Graph class, Graph theory, Maximum cut, Maximum cuts, Parameterized, Parameterization, Parameterized complexity, Polynomial approximation, Polynomial-time, Proper interval graph, Proper interval graphs, Max-cut
Kaynak
Theoretical Computer Science
WoS Q Değeri
Q4
Scopus Q Değeri
Q2
Cilt
898
Sayı
Künye
Boyacı, A., Ekim, T. & Shalom, M. (2021). On the maximum cardinality cut problem in proper interval graphs and related graph classes. Theoretical Computer Science, 898, 20-29. doi:10.1016/j.tcs.2021.10.014
