Namely, we show thatMaxCut is polynomial-time solvable for co-bipartite graphs that can be factored to bounded treewidth graphs using bimodular decomposition.
📌 3 Key Takeaways
🎯
Objective & Hypothesis:The maximum cardinality cut (MaxCut) problem remains NP-complete for co-bipartite graphs and for split graphs.
📊
Key Findings & Data:Based on modular decomposition, in [3] it is shown that MaxCut is polynomial-time solvable for graphs that are factorable to bounded treewidth graphs.
💡
Conclusion & Impact:Namely, we show thatMaxCut is polynomial-time solvable for co-bipartite graphs that can be factored to bounded treewidth graphs using bimodular decomposition.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Domain Parameters
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.
🔖
Cite This Article
Boyacı, A., Shalom, M. (2022). A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition. Turkish Journal of Mathematics and Computer Science, Cilt: 13 - Sayı: 1, 182–191. https://ajindex.com/articles/609057
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
Bodlaender, H.L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25(6)(1996), 1305–1317
Bodlaender, H.L., Jansen, K., On the complexity of the maximum cut problem, Nord. J. Comput., 7(2000), 14–31
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
Ekim, T., Boyacı, A., Shalom, M., The maximum cardinality cut problem in co-bipartite chain graphs, Journal of Combinatorial Optimization, 35(2018), 250–265
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
Gallai, T., Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica, 18(1)(1967), 25–66
Guruswami, V., Maximum cut on line and total graphs, Discrete Applied Mathematics, 92(2-3)(1999), 217–221
Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput., 4(3):221–225, 1975
Heggernes, P., Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nord. J. Comput., 14(1-2)(2007), 87–108
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
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.