Research Article
BibTex RIS Cite
Year 2021, , 182 - 191, 30.06.2021
https://doi.org/10.47000/tjmcs.748563

Abstract

References

  • [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] Bodlaender, H.L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25(6)(1996), 1305–1317.
  • [3] Bodlaender, H.L., Jansen, K., On the complexity of the maximum cut problem, Nord. J. Comput., 7(2000), 14–31.
  • [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] 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] 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] Gallai, T., Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica, 18(1)(1967), 25–66.
  • [8] Guruswami, V., Maximum cut on line and total graphs, Discrete Applied Mathematics, 92(2-3)(1999), 217–221.
  • [9] Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput., 4(3):221–225, 1975.
  • [10] Heggernes, P., Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nord. J. Comput., 14(1-2)(2007), 87–108.
  • [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] 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.

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

Year 2021, , 182 - 191, 30.06.2021
https://doi.org/10.47000/tjmcs.748563

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.

References

  • [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] Bodlaender, H.L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM J. Comput., 25(6)(1996), 1305–1317.
  • [3] Bodlaender, H.L., Jansen, K., On the complexity of the maximum cut problem, Nord. J. Comput., 7(2000), 14–31.
  • [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] 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] 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] Gallai, T., Transitiv orientierbare graphen, Acta Mathematica Academiae Scientiarum Hungarica, 18(1)(1967), 25–66.
  • [8] Guruswami, V., Maximum cut on line and total graphs, Discrete Applied Mathematics, 92(2-3)(1999), 217–221.
  • [9] Hadlock, F., Finding a maximum cut of a planar graph in polynomial time, SIAM J. Comput., 4(3):221–225, 1975.
  • [10] Heggernes, P., Kratsch, D., Linear-time certifying recognition algorithms and forbidden induced subgraphs, Nord. J. Comput., 14(1-2)(2007), 87–108.
  • [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] 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.
There are 12 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Articles
Authors

Arman Boyacı This is me 0000-0002-5613-1718

Mordechai Shalom 0000-0002-2688-5703

Publication Date June 30, 2021
Published in Issue Year 2021

Cite

APA Boyacı, A., & Shalom, M. (2021). A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition. Turkish Journal of Mathematics and Computer Science, 13(1), 182-191. https://doi.org/10.47000/tjmcs.748563
AMA Boyacı A, Shalom M. A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition. TJMCS. June 2021;13(1):182-191. doi:10.47000/tjmcs.748563
Chicago Boyacı, Arman, and Mordechai Shalom. “A Maximum Cardinality Cut Algorithm for Co-Bipartite and Split Graphs Using Bimodular Decomposition”. Turkish Journal of Mathematics and Computer Science 13, no. 1 (June 2021): 182-91. https://doi.org/10.47000/tjmcs.748563.
EndNote Boyacı A, Shalom M (June 1, 2021) A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition. Turkish Journal of Mathematics and Computer Science 13 1 182–191.
IEEE A. Boyacı and M. Shalom, “A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition”, TJMCS, vol. 13, no. 1, pp. 182–191, 2021, doi: 10.47000/tjmcs.748563.
ISNAD Boyacı, Arman - Shalom, Mordechai. “A Maximum Cardinality Cut Algorithm for Co-Bipartite and Split Graphs Using Bimodular Decomposition”. Turkish Journal of Mathematics and Computer Science 13/1 (June 2021), 182-191. https://doi.org/10.47000/tjmcs.748563.
JAMA Boyacı A, Shalom M. A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition. TJMCS. 2021;13:182–191.
MLA Boyacı, Arman and Mordechai Shalom. “A Maximum Cardinality Cut Algorithm for Co-Bipartite and Split Graphs Using Bimodular Decomposition”. Turkish Journal of Mathematics and Computer Science, vol. 13, no. 1, 2021, pp. 182-91, doi:10.47000/tjmcs.748563.
Vancouver Boyacı A, Shalom M. A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition. TJMCS. 2021;13(1):182-91.