Near-Bipartiteness on graphs having small dominating sets: Structural characterization and algorithms
Resumo
The Near-Bipartiteness problem asks for a partition of the vertex set of a graph G = (V,E) into two subsets S and F, where S forms an independent set and F induces a forest. Despite its NP-completeness, even for graphs with a diameter three, we explore this problem on graphs with a dominating edge or small dominating sets. Our work presents a polynomial-time algorithm for Near-Bipartiteness on graphs with a dominating edge, a particular case of graphs with diameter three. In addition, we prove that Connected Near-Bipartiteness, the variant where the forest must be connected, is NP-complete on the same class. Moreover, we also establish the NP-hardness of Independent Feedback Vertex Set and Acyclic Vertex Cover on this class of graphs. In addition, by extending our approach to graphs with bounded dominating sets, we achieve a huge improvement, obtaining an O(n2 · m)-time algorithm for Near-Bipartiteness on P5-free graphs, improving upon the current state-of-the-art time complexity of O(n16).
Referências
Achlioptas, D. (1997). The complexity of G-free colourability. Discrete Mathematics, 165-166:21–30.
Agrawal, A., Gupta, S., Saurabh, S., and Sharma, R. (2017). Improved algorithms and combinatorial bounds for independent feedback vertex set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
Aspvall, B., Plass, M., and Tarjan, R. (1982). A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 14(4).
Bacsó, G. and Tuza, Z. (1990). Dominating cliques in P5-free graphs. Periodica Mathematica Hungarica, 21(4):303–308.
Bang-Jensen, J. and Bessy, S. (2019). Degree-constrained 2-partitions of graphs. Theoretical Computer Science, 776:64–74.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2017). Recognizing graphs close to bipartite graphs. In MFCS 2017.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131:26–32.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2019). Independent feedback vertex set for P5-free graphs. Algorithmica, 81(4):1342–1369.
Borodin, O., Kostochka, A., and Yancey, M. (2013). On 1-improper 2-coloring of sparse graphs. Discrete Math., 313(22):2638–2649.
Brandstädt, A., Brito, S., Klein, S., Nogueira, L. T., and Protti, F. (2013). Cycle transversals in perfect graphs and cographs. Theoretical Computer Science, 469:15–23.
Brandstädt, A., Le, V. B., and Szymczak, T. (1998). The complexity of some problems related to graph 3-colorability. Discrete Applied Mathematics, 89(1):59–73.
Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited. J. Graph Theory, 24(3):205–219.
da Cruz, M. L. L. (2023). Near-bipartiteness on graphs having small dominating sets. Master’s thesis, Universidade Federal Fluminense (UFF).
Dross, F., Montassier, M., and Pinlou, A. (2017). Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. European Journal of Combinatorics, 66:81–94.
Garey, M. R. and Johnson, D. S. (1979). Computers and intractability: A Guide to the Theory of NP-completeness, volume 174.
Grötschel, M., Lovász, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. Ann. Discrete Math, 21:325–356.
Karp, R. M. (1972). Reducibility among combinatorial problems. Springer.
Li, S. and Pilipczuk, M. (2020). An improved FPT algorithm for independent feedback vertex set. Theory of Computing Systems, 64(8):1317–1330.
Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2017). Decycling with a matching. Infor. Proc. Letters, 124:26 – 29.
Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2021). On the computational complexity of the bipartizing matching problem. Annals of Operations Research.
Misra, N., Narayanaswamy, N., Raman, V., and Shankar, B. S. (2013). Solving min ones 2-sat as fast as vertex cover. Theoretical Computer Science, 506.
Misra, N., Philip, G., Raman, V., and Saurabh, S. (2012). On parameterized independent feedback vertex set. Theoretical Computer Science, 461:65–75.
Protti, F. and 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, 20(2).
Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the tenth annual ACM Symposium on Theory of Computing.
Yang, A. and Yuan, J. (2006). Partition the vertices of a graph into one independent set and one acyclic set. Discrete Mathematics, 306(12).
Agrawal, A., Gupta, S., Saurabh, S., and Sharma, R. (2017). Improved algorithms and combinatorial bounds for independent feedback vertex set. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.
Aspvall, B., Plass, M., and Tarjan, R. (1982). A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 14(4).
Bacsó, G. and Tuza, Z. (1990). Dominating cliques in P5-free graphs. Periodica Mathematica Hungarica, 21(4):303–308.
Bang-Jensen, J. and Bessy, S. (2019). Degree-constrained 2-partitions of graphs. Theoretical Computer Science, 776:64–74.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2017). Recognizing graphs close to bipartite graphs. In MFCS 2017.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2018). Independent feedback vertex sets for graphs of bounded diameter. Information Processing Letters, 131:26–32.
Bonamy, M., Dabrowski, K. K., Feghali, C., Johnson, M., and Paulusma, D. (2019). Independent feedback vertex set for P5-free graphs. Algorithmica, 81(4):1342–1369.
Borodin, O., Kostochka, A., and Yancey, M. (2013). On 1-improper 2-coloring of sparse graphs. Discrete Math., 313(22):2638–2649.
Brandstädt, A., Brito, S., Klein, S., Nogueira, L. T., and Protti, F. (2013). Cycle transversals in perfect graphs and cographs. Theoretical Computer Science, 469:15–23.
Brandstädt, A., Le, V. B., and Szymczak, T. (1998). The complexity of some problems related to graph 3-colorability. Discrete Applied Mathematics, 89(1):59–73.
Cowen, L., Goddard, W., and Jesurum, C. E. (1997). Defective coloring revisited. J. Graph Theory, 24(3):205–219.
da Cruz, M. L. L. (2023). Near-bipartiteness on graphs having small dominating sets. Master’s thesis, Universidade Federal Fluminense (UFF).
Dross, F., Montassier, M., and Pinlou, A. (2017). Partitioning a triangle-free planar graph into a forest and a forest of bounded degree. European Journal of Combinatorics, 66:81–94.
Garey, M. R. and Johnson, D. S. (1979). Computers and intractability: A Guide to the Theory of NP-completeness, volume 174.
Grötschel, M., Lovász, L., and Schrijver, A. (1984). Polynomial algorithms for perfect graphs. Ann. Discrete Math, 21:325–356.
Karp, R. M. (1972). Reducibility among combinatorial problems. Springer.
Li, S. and Pilipczuk, M. (2020). An improved FPT algorithm for independent feedback vertex set. Theory of Computing Systems, 64(8):1317–1330.
Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2017). Decycling with a matching. Infor. Proc. Letters, 124:26 – 29.
Lima, C. V., Rautenbach, D., Souza, U. S., and Szwarcfiter, J. L. (2021). On the computational complexity of the bipartizing matching problem. Annals of Operations Research.
Misra, N., Narayanaswamy, N., Raman, V., and Shankar, B. S. (2013). Solving min ones 2-sat as fast as vertex cover. Theoretical Computer Science, 506.
Misra, N., Philip, G., Raman, V., and Saurabh, S. (2012). On parameterized independent feedback vertex set. Theoretical Computer Science, 461:65–75.
Protti, F. and 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, 20(2).
Schaefer, T. J. (1978). The complexity of satisfiability problems. In Proceedings of the tenth annual ACM Symposium on Theory of Computing.
Yang, A. and Yuan, J. (2006). Partition the vertices of a graph into one independent set and one acyclic set. Discrete Mathematics, 306(12).
Publicado
21/07/2024
Como Citar
CRUZ, Maria Luíza López da; SOUZA, Uéverton S.; BRAVO, Raquel.
Near-Bipartiteness on graphs having small dominating sets: Structural characterization and algorithms. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 37. , 2024, Brasília/DF.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 118-127.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2024.2585.
