- Turkish Journal of Mathematics and Computer Science
- Vol: 13 Issue: 1
- A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition
A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition
Authors : Arman BOYACI, Mordechai SHALOM
Pages : 182-191
Doi:10.47000/tjmcs.748563
View : 4 | Download : 2
Publication Date : 2021-06-30
Article Type : Research
Abstract :The maximum cardinality cut (MaxCut) problem remains NP-complete for co-bipartite graphs and for split graphs. Based on modular decomposition, in [3] it is shown that MaxCut is polynomial-time solvable for graphs that are factorable to bounded treewidth graphs. However, this approach fails in co-bipartite graphs because the modules of a co-bipartite graph are exactly twins and connected components. In this work we extend the result of [3] to co-bipartite graphs using the concept of bimodules and bimodular decomposition proposed in [6]. Namely, we show thatMaxCut is polynomial-time solvable for co-bipartite graphs that can be factored to bounded treewidth graphs using bimodular decomposition.Keywords : Maximum cardinality cut, bimodular decomposition, split graphs.