A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition

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.

References

1. [1] Barahona, F., Grötschel, M., Jünger, M., Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout design, Operations Research, 36(3)(1988), 493–513.
2. [2] Bodlaender, H.L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25(6)(1996), 1305–1317.
3. [3] Bodlaender, H.L., Jansen, K., On the complexity of the maximum cut problem, Nord. J. Comput., 7(2000), 14–31.
4. [4] Diaz,J., Kaminski, M., Max-cut and max-bisection are NP-hard on unit disk graphs, Theoretical Computer Science, 377(1–3)(2007), 271–276.
5. [5] Ekim, T., Boyacı, A., Shalom, M., The maximum cardinality cut problem in co-bipartite chain graphs, Journal of Combinatorial Optimization, 35(2018), 250–265.
6. [6] Fouquet, J-L., Habib, M., De Montgolfier, F., Vanherpe, J-M., Bimodular decomposition of bipartite graphs, In 30th International Workshop on Graph Theoretic Concepts in Computer Science, WG, 117–128, 2004.
7. [7] Gallai, T., Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica, 18(1)(1967), 25–66.
8. [8] Guruswami, V., Maximum cut on line and total graphs, Discrete Applied Mathematics, 92(2-3)(1999), 217–221.

9. [9] Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput., 4(3):221–225, 1975.
10. [10] Heggernes, P., Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nord. J. Comput., 14(1-2)(2007), 87–108.
11. [11] Karp, R.M., Reducibility among combinatorial problems, In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds), Complexity of Computer Computations, The IBM Research Symposia Series, Springer, 85–103, 1972.
12. [12] Tedder, M., Corneil, D., Habib, M., Paul, C., Simpler linear-time modular decomposition via recursive factorizing permutations, In: Aceto, L., Damgard, I., Goldberg, L., Halldorsson, M.M., Ingolfsdattir, A., Walukiewicz, I. (eds), Automata, Languages and Programming, volume 5125 of Lecture Notes in Computer Science, Springer, 634–645, 2008.