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 : 9 | Download : 10

Publication Date : 2021-06-30

Article Type : Research Paper

Abstract :The maximum cardinality cut insert ignore into journalissuearticles values(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