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, 2029.doi:10.1016/j.tcs.2021.10.014Abstract
Although it has been claimed in two different papers that the maximum cardinality cut problem is polynomialtime 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 nonempty 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 wellknown cliquewidth parameter. Specifically, we define an (α,β,δ)cliquewidth decomposition of a graph as a cliquewidth 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 (α,β,δ)cliquewidth decomposition.
Source
Theoretical Computer ScienceThe following license files are associated with this item:
Related items
Showing items related by title, author, creator and subject.

Crossing minimization in weighted bipartite graphs
Çakıroğlu, Olca Arda; Erten, Cesim; Karataş, Ömer; Sözdinler, Melih (Elsevier B.V., 200912)Given a bipartite graph G = (L0, L1, E) and a fixed ordering of the nodes in L0, the problem of finding an ordering of the nodes in L1 that minimizes the number of crossings has received much attention in literature. The ... 
On arithmeticgeometric index (GA) and edge GA index
Aytaç, Vecdi; Turacı, Tufan (Işık University Press, 2018)Let G(V (G), E(G)) be a simple connected graph and dG(u) be the degree of the vertex u. Topological indices are numerical parameters of a graph which are invariant under graph isomorphisms. Recently, people are studying ... 
On star chromatic number of prism graph families
Kowsalya, Venkatesan; Vivin, Joseph Vernold; Kumar, S. Vimal (Işık University Press, 2019)In this paper, we find the star chromatic number χs for the central graph of prism graph C(Yn), line graph of prism graph L(Yn), middle graph of prism graph M(Yn) and the total graph of prism graph T(Yn) for all n ≥ 3.