On the maximum cardinality cut problem in proper interval graphs and related graph classes
Citation
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.014Abstract
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.
Source
Theoretical Computer ScienceVolume
898The following license files are associated with this item:
Related items
Showing items related by title, author, creator and subject.
-
Balanced rank distribution labeling of ladder graphs, complete graphs and complete bipartite graphs
Hemalatha, Palanisamy; Gokilamani, S. (Işık University Press, 2021)A balanced rank distribution labeling of a graph G of order n is a new kind of vertex labeling from {1, 2, 3, ..., k}(n <= k is an element of Z(+)) which leads to a balanced edge labeling of G called edge ranks. In this ... -
Hub-integrity of splitting graph and duplication of graph elements
Mahde, Sultan Senan; Mathad, Veena (Işık University Press, 2016-01-08)The hub-integrity of a graph G = (V (G), E(G)) is denoted as HI(G) and defined by HI(G) = min{|S| + m(G − S), S is a hub set of G}, where m(G − S) is the order of a maximum component of G − S. In this paper, we discuss ... -
On certain topological indices of the derived graphs of subdivision graphs
Hosamani, Sunilkumar M.; Lokesha, Veerebradiah; Cangül, İsmail Naci; Devendraiah, K. M. (Işık University Press, 2016-03-11)The derived graph [G]† of a graph G is the graph having the same vertex set as G, with two vertices of [G]† being adjacent if and only if their distance in G is two. Topological indices are valuable in the study of QSAR/QSPR. ...