On the computational complexity of the bipartizing matching problem | Annals of Operations Research Skip to main content
Log in

On the computational complexity of the bipartizing matching problem

  • S.I.: CLAIO 2018
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Given a graph \(G=(V,E)\), an edge bipartization set of G is a subset \(E'\subseteq E(G)\) such that \(G'=(V,E{\setminus } E')\) is bipartite. An edge bipartization set that is also a matching of G is called a bipartizing matching of G. Let \({\mathscr {BM}}\) be the family of all graphs admitting a bipartizing matching. Although every graph has an edge bipartization set, the problem of recognizing graphs G having bipartizing matchings (\(G\in \mathscr {BM}\)) is challenging. A (kd)-coloring of a graph G is a k-coloring of V(G) such that each vertex of G has at most d neighbors with the same color as itself. Clearly a (k, 0)-coloring is a proper vertex k-coloring of G and, for any \(d>0\), the k-coloring is non-proper, also known as defective. A graph belongs to \(\mathscr {BM}\) if and only if it admits a (2, 1)-coloring. Lovász (1966) proved that for any integer \(k>0\), any graph of maximum degree \(\varDelta \) admits a \(\left( k,\lfloor \varDelta /k \rfloor \right) \)-coloring. In this paper, we show that it is NP-complete to determine whether a 3-colorable planar graph of maximum degree 4 belongs to \(\mathscr {BM}\), i.e., (2, 1)-colorable. Besides, we show that it is NP-complete to determine whether planar graphs of maximum degree 6 or 8 admit a (2, 2) or (2, 3)-coloring, respectively. Due to Lovász (1966), our results are tight in the sense that on graphs with maximum degree three, five, and seven, there always exists a (2, 1), (2, 2), and (2, 3)-coloring, respectively. Finally, we present polynomial-time algorithms for particular graph classes, besides some remarks on the parameterized complexity of the problem of recognizing graphs in \({\mathscr {BM}}\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  • Abdullah, A. (1992). On graph bipartization. In: ISCAS ’92 (Vol. 4, pp. 1847–1850)

  • Agrawal, A., Jain, P., Kanesh, L., Misra, P., & Saurabh, S. (2019). Exploring the Kernelization Borders for Hitting Cycles. In: 13th international symposium on parameterized and exact computation (IPEC 2018), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, Leibniz International Proceedings in Informatics (LIPIcs) (Vol. 115, pp. 14:1–14:14).

  • Alon, N., & Stav, U. (2009). Hardness of edge-modification problems. Theoretical Computer Science, 410(47–49), 4920–4927.

    Article  Google Scholar 

  • Andrews, J., & Jacobson, M. (1985). On a generalization of chromatic number. In: Proc. sixteenth southeastern international conference on combinatorics, graph theory and computing (Vol. 47, pp. 18–33).

  • Angelini, P., Bekos, M. A., De Luca, F., Didimo, W., Kaufmann, M., Kobourov, S., et al. (2017). Vertex-coloring with defects. Journal of Graph Algorithms and Applications, 21(3), 313–340.

    Article  Google Scholar 

  • Axenovich, M., Ueckerdt, T., & Weiner, P. (2017). Splitting planar graphs of girth 6 into two linear forests with short paths. Journal of Graph Theory, 85(3), 601–618.

    Article  Google Scholar 

  • Bang-Jensen, J., & Bessy, S. (2019). Degree-constrained 2-partitions of graphs. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2018.12.023.

  • Bodlaender, H. L. (1998). A partial \(k\)-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209(1–2), 1–45.

    Article  Google Scholar 

  • Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., & Paulusma, D. (2018). Independent feedback vertex set for P\(_5\)-free graphs. Algorithmica. https://doi.org/10.1007/s00453-018-0474-x.

  • Borodin, O., Kostochka, A., & Yancey, M. (2013). On \(1\)-improper \(2\)-coloring of sparse graphs. Discrete Mathematics, 313(22), 2638–2649.

    Article  Google Scholar 

  • Brandstädt, A., Dragan, F. F., Le, H. O., & Mosca, R. (2005). New graph classes of bounded clique-width. Theory of Computing Systems, 38(5), 623–645.

    Article  Google Scholar 

  • Brandstädt, A., Engelfriet, J., Le, H. O., & Lozin, V. V. (2006a). Clique-width for \(4\)-vertex forbidden subgraphs. Theory of Computing Systems, 39(4), 561–590.

    Article  Google Scholar 

  • Brandstädt, A., Klembt, T., & Mahfud, S. (2006b). \(P_6\)- and triangle-free graphs revisited: structure and bounded clique-width. Discrete Mathematics & Theoretical Computer Science, 8, 173–188.

    Article  Google Scholar 

  • Burzyn, P., Bonomo, F., & Durán, G. (2006). NP-completeness results for edge modification problems. Discrete Applied Mathematics, 154(13), 1824–1844.

    Article  Google Scholar 

  • Camby, E., & Schaudt, O. (2016). A new characterization of \(P_k\)-free graphs. Algorithmica, 75(1), 205–217.

    Article  Google Scholar 

  • Carneiro, A. D. A., Protti, F., & Souza, U. S. (2019). Deadlock resolution in wait-for graphs by vertex/arc deletion. Journal of Combinatorial Optimization, 37(2), 546–562. https://doi.org/10.1007/s10878-018-0279-5.

    Article  Google Scholar 

  • Choi, H. A., Nakajima, K., & Rim, C. S. (1989). Graph bipartization and via minimization. SIAM Journal on Discrete Mathematics, 2(1), 38–47.

    Article  Google Scholar 

  • Chuangpishit, H., Lafond, M., & Narayanan, L. (2018). Editing graphs to satisfy diversity requirements. In D. Kim, R. N. Uma & A. Zelikovsky (Eds.), Combinatorial Optimization and Applications (COCOA 2018) (pp. 154–168). Cham: Springer.

  • Courcelle, B. (1990). The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information & Computation, 85(1), 12–75.

  • Courcelle, B. (1997). Handbook of graph grammars and computing by graph transformation. In G. Rozenberg (Ed.), The expression of graph properties and graph transformations in monadic second-order logic (pp. 313–400). River Edge: World Scientific Publishing Co., Inc.

    Google Scholar 

  • Courcelle, B., & Engelfriet, J. (2012). Graph structure and monadic second-order logic: a language-theoretic approach. New York: Cambridge University Press.

    Book  Google Scholar 

  • Courcelle, B., & Mosbah, M. (1993). Monadic second-order evaluations on tree-decomposable graphs. Theoretical Computer Science, 109(1–2), 49–82.

    Article  Google Scholar 

  • Courcelle, B., Makowsky, J. A., & Rotics, U. (2000). Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems, 33(2), 125–150.

    Article  Google Scholar 

  • Cowen, L., Cowen, R., & Woodall, D. (1986). Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency. Journal of Graph Theory, 10, 187–195.

    Article  Google Scholar 

  • Cowen, L., Goddard, W., & Jesurum, C. E. (1997). Defective coloring revisited. Journal of Graph Theory, 24(3), 205–219.

    Article  Google Scholar 

  • Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Berlin: Springer.

    Book  Google Scholar 

  • Diestel, R. (2010). Graph theory (4th ed., Vol. 173). Berlin: Springer.

  • Dorbec, P., Montassier, M., & Ochem, P. (2014). Vertex partitions of graphs into cographs and stars. Journal of Graph Theory, 75(1), 75–90. https://doi.org/10.1002/jgt.21724.

    Article  Google Scholar 

  • Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Texts in computer science. Berlin: Springer.

    Book  Google Scholar 

  • Eaton, N., & Hull, T. (1999). Defective list colorings of planar graphs. Bulletin of the Institute of Combinatorics and its Applications, 25, 79–87.

    Google Scholar 

  • Furmańczyk, H., Kubale, M., & Radziszowski, S. (2016). On bipartization of cubic graphs by removal of an independent set. Discrete Applied Mathematics, 209, 115–121.

    Article  Google Scholar 

  • García-Vázquez, P. (2016). On the bipartite vertex frustration of graphs. Electronic Notes in Discrete Mathematics, 54, 289–294. https://doi.org/10.1016/j.endm.2016.09.050.

    Article  Google Scholar 

  • Garey, M., Johnson, D., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3), 237–267.

    Article  Google Scholar 

  • Gimbel, J., & Nešetřil, J. (2010). Partitions of graphs into cographs. Discrete Mathematics, 310(24), 3437–3445. https://doi.org/10.1016/j.disc.2010.07.011.

    Article  Google Scholar 

  • Golumbic, M. C., & Rotics, U. (2000). On the clique-width of some perfect graph classes. International Journal of Foundations of Computer Science, 11(03), 423–443.

    Article  Google Scholar 

  • Guillemot, S., Havet, F., Paul, C., & Perez, A. (2012). On the (non-)existence of polynomial kernels for \(p\)-free edge modification problems. Algorithmica, 65(4), 900–926.

    Article  Google Scholar 

  • Harary, F., & Jones, K. (1985). Conditional colorability ii: Bipartite variations. In: Proc. sundance cont. combinatorics and related topics, congr. numer. (Vol. 50, pp. 205–2018)

  • Hopcroft, J., & Tarjan, R. (1974). Efficient planarity testing. Journal of the ACM, 21(4), 549–568.

    Article  Google Scholar 

  • Lampis, M. (2012). Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1), 19–37.

    Article  Google Scholar 

  • Lima, C. V., Rautenbach, D., Souza, U. S., & Szwarcfiter, J. L. (2017). Decycling with a matching. Information Processing Letters, 124, 26–29.

    Article  Google Scholar 

  • Lovász, L. (1966). On decomposition of graphs. Studia Scientiarum Mathematicarum Hungarica, 1, 237–238.

    Google Scholar 

  • Mulzer, W., & Rote, G. (2008). Minimum-weight triangulation is NP-hard. Journal of the ACM, 55(2), 1–29.

    Article  Google Scholar 

  • Natanzon, A., Shamir, R., & Sharan, R. (2001). Complexity classification of some edge modification problems. Discrete Applied Mathematics, 113(1), 109–128.

    Article  Google Scholar 

  • Protti, F., & Souza, U. S. (2018). Decycling a graph by the removal of a matching: New algorithmic and structural aspects in some classes of graphs. Discrete Mathematics & Theoretical Computer Science. https://doi.org/10.23638/DMTCS-20-2-15.

  • Robertson, N., & Seymour, P. (1986). Graph minors ii algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309–322.

    Article  Google Scholar 

  • Schaefer, TJ. (1978). The complexity of satisfiability problems. In: STOC ’78 (pp. 216–226)

  • Thorup, M. (1998). All structured programs have small tree width and good register allocation. Information and Computation, 142(2), 159–181.

    Article  Google Scholar 

  • Yannakakis, M. (1978). Node-and edge-deletion NP-complete problems. In: STOC ’78 (pp. 253–264)

  • Yannakakis, M. (1981). Edge-deletion problems. SIAM Journal on Computing, 10(2), 297–309.

    Article  Google Scholar 

  • Yarahmadi, Z., & Ashrafi, A. R. (2014). A fast algorithm for computing bipartite edge frustration number of \((3,6)\)-fullerenes. Journal of Theoretical and Computational Chemistry, 13(02), 1450014–1–1450014–11.

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Carlos V. G. C. Lima.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This study was financed in part by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - Brasil (CAPES) Finance Code 001, by the Conselho Nacional de Desenvolvimento Científico e Tecnológico - Brasil (CNPq) - Grant Numbers: (CNPq/DAAD2015SWE/290021/2015-4, 303726/2017-2, 309832/2020-9), and FAPERJ (Grant Number: E-26/203.272/2017). A conference version appeared in the Proc. of the 12th Annual International Conference on Combinatorial Optimization and Applications (COCOA), Volume 11346, pages 198–213, Atlanta, USA, December 2018.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lima, C.V.G.C., Rautenbach, D., Souza, U.S. et al. On the computational complexity of the bipartizing matching problem. Ann Oper Res 316, 1235–1256 (2022). https://doi.org/10.1007/s10479-021-03966-9

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-021-03966-9

Keywords

Mathematics Subject Classification

Navigation