On (in)tractability of connection and cut problems
Resumo
This work addresses connection and cut problems from the viewpoint of graph classes and computational complexity, classic and parameterized. Regarding connection problems, we investigate the so-called TERMINAL CONNECTION problem (TCP), which can be seen as a generalisation of the classical STEINER TREE problem. We propose several complexity results for TCP, when restricted to specific graph classes, and some of its input parameters are fixed. As for cut problems, we analyse the complexity of the classical MAXCUT problem. We introduce the first complexity classification for the problem on interval graphs of bounded interval count. In addition, we prove the NP-completeness of MAXCUT on permutation graphs, settling a question posed by David S. Johnson in the Ongoing Guide to NP-completeness, which has been open since 1985. Finally, we consider the problem of computing the zig-zag number of a directed graph, which is a directed width measure defined over cuts of a graph.
Referências
Adhikary, R., Bose, K., Mukherjee, S., and Roy, B. (2021). Complexity of maximum cut on interval graphs. In 37th International Symposium on Computational Geometry, SoCG 2021, volume 189 of LIPIcs, pages 7:1–7:11.
Barát, J. (2006). Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics, 22(2):161–172.
Bergougnoux, B. and Kanté, M. (2019). Fast exact algorithms for some connectivity problems parameterized by clique-width. Theoretical Computer Science, 782:30 – 53.
Bodlaender, H. L., de Figueiredo, C. M. H., Gutierrez, M., Kloks, T., and Niedermeier, R. (2004). SIMPLE MAX-CUT for split-indifference graphs and graphs with few P4s. In Experimental and Efficient Algorithms, Third International Workshop, WEA 2004, volume 3059 of Lecture Notes in Computer Science, pages 87–99.
Bodlaender, H. L., Kloks, T., and Niedermeier, R. (1999). SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s. Electronic Notes in Discrete Mathematics, 3:19–26.
Boyaci, A., Ekim, T., and Shalom, M. (2017). A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters, 121:29–33.
Colbourn, C. J. and Stewart, L. K. (1990). Permutation graphs: connected domination and Steiner trees. Discrete Mathematics, 86(1-3):179–189.
Courcelle, B. (1990). The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12–75.
de Figueiredo, C. M. H., de Melo, A. A., de S. Oliveira, F., and Silva, A. (2021). Maximum cut on interval graphs of interval count four is NP-complete. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs, pages 38:1–38:15.
de Figueiredo, C. M. H., de Melo, A. A., de S. Oliveira, F., and Silva, A. (2023a). Maxcut on permutation graphs is NP-complete. Journal of Graph Theory. https://doi.org/10.1002/jgt.22948 (forthcoming).
de Figueiredo, C. M. H., de Melo, A. A., de S. Oliveira, F., and Silva, A. (2023b). Maximum cut on interval graphs of interval count four is NP-complete. Discrete & Computational Geometry. https://doi.org/10.1007/s00454-023-00508-x (forthcoming).
de Figueiredo, C. M. H., de Melo, A. A., Sasaki, D., and Silva, A. (2022). Revising Johnson’s table for the 21st century. Discrete Applied Mathematics, 323:184–200.
de Melo, A. A. (2022). On (in)tractability of connection and cut problems. PhD thesis, Universidade Federal do Rio de Janeiro.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2021a). On the terminal connection problem. In 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, volume 12607 of Lecture Notes in Computer Science, pages 278–292.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2021b). On undirected two-commodity integral flow, disjoint paths and strict terminal connection problems. Networks, 77(4):559–571.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2022). The strict terminal connection problem on chordal bipartite graphs. Matemática Contemporânea, 48(14):137–145.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2023). On the computational difficulty of the terminal connection problem. RAIRO Theoretical Informatics and Applications.
de Melo, A. A. and de Oliveira Oliveira, M. (2022). Second-order finite automata. Theory of Computing Systems, 66(4):861–909.
de Melo, A. A., Figueiredo, C. M. H., and Souza, U. S. (2020). A multivariate analysis of the strict terminal connection problem. Journal of Computer and System Sciences, 111:22–41.
de Oliveira Oliveira, M. (2013). Subgraphs satisfying MSO properties on z-topologically orderable digraphs. In Parameterized and Exact Computation, IPEC 2013, volume 8246 of Lecture Notes in Computer Science, pages 123–136.
Dourado, M. C., de Figueiredo, C. M. H., de Melo, A. A., de Oliveira Oliveira, M., and Souza, U. S. (2022). Computing the zig-zag number of directed graphs. Discrete Applied Mathematics, 312:86–105.
Dourado, M. C., Oliveira, R. A., Protti, F., and Souza, U. S. (2014). Design of connection networks with bounded number of non-terminal vertices. Matemática Contemporânea, 42(14):39–47.
Garey, M. R., Johnson, D. S., and Stockmeyer, L. J. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237–267.
Johnson, D. S. (1985). The NP-completeness column: An ongoing guide. Journal of Algorithms, 6(3):434–451.
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R. (2001). Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138–154.
Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA.
Kratochvíl, J., Masarík, T., and Novotná, J. (2020). U-bubble model for mixed unit interval graphs and its applications: The maxcut problem revisited. In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, volume 170 of LIPIcs, pages 57:1–57:14.
Leibowitz, R., Assmann, S. F., and Peck, G. W. (1982). The interval count of a graph. SIAM Journal on Algebraic Discrete Methods, 3(4):485–494.
Müller, H. and Brandstädt, A. (1987). The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theoretical Computer Science, 53(2-3):257–265.
White, K., Farber, M., and Pulleyblank, W. (1985). Steiner trees, connected domination and strongly chordal graphs. Networks, 15(1):109–124.
Barát, J. (2006). Directed path-width and monotonicity in digraph searching. Graphs and Combinatorics, 22(2):161–172.
Bergougnoux, B. and Kanté, M. (2019). Fast exact algorithms for some connectivity problems parameterized by clique-width. Theoretical Computer Science, 782:30 – 53.
Bodlaender, H. L., de Figueiredo, C. M. H., Gutierrez, M., Kloks, T., and Niedermeier, R. (2004). SIMPLE MAX-CUT for split-indifference graphs and graphs with few P4s. In Experimental and Efficient Algorithms, Third International Workshop, WEA 2004, volume 3059 of Lecture Notes in Computer Science, pages 87–99.
Bodlaender, H. L., Kloks, T., and Niedermeier, R. (1999). SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s. Electronic Notes in Discrete Mathematics, 3:19–26.
Boyaci, A., Ekim, T., and Shalom, M. (2017). A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters, 121:29–33.
Colbourn, C. J. and Stewart, L. K. (1990). Permutation graphs: connected domination and Steiner trees. Discrete Mathematics, 86(1-3):179–189.
Courcelle, B. (1990). The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12–75.
de Figueiredo, C. M. H., de Melo, A. A., de S. Oliveira, F., and Silva, A. (2021). Maximum cut on interval graphs of interval count four is NP-complete. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs, pages 38:1–38:15.
de Figueiredo, C. M. H., de Melo, A. A., de S. Oliveira, F., and Silva, A. (2023a). Maxcut on permutation graphs is NP-complete. Journal of Graph Theory. https://doi.org/10.1002/jgt.22948 (forthcoming).
de Figueiredo, C. M. H., de Melo, A. A., de S. Oliveira, F., and Silva, A. (2023b). Maximum cut on interval graphs of interval count four is NP-complete. Discrete & Computational Geometry. https://doi.org/10.1007/s00454-023-00508-x (forthcoming).
de Figueiredo, C. M. H., de Melo, A. A., Sasaki, D., and Silva, A. (2022). Revising Johnson’s table for the 21st century. Discrete Applied Mathematics, 323:184–200.
de Melo, A. A. (2022). On (in)tractability of connection and cut problems. PhD thesis, Universidade Federal do Rio de Janeiro.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2021a). On the terminal connection problem. In 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, volume 12607 of Lecture Notes in Computer Science, pages 278–292.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2021b). On undirected two-commodity integral flow, disjoint paths and strict terminal connection problems. Networks, 77(4):559–571.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2022). The strict terminal connection problem on chordal bipartite graphs. Matemática Contemporânea, 48(14):137–145.
de Melo, A. A., de Figueiredo, C. M. H., and Souza, U. S. (2023). On the computational difficulty of the terminal connection problem. RAIRO Theoretical Informatics and Applications.
de Melo, A. A. and de Oliveira Oliveira, M. (2022). Second-order finite automata. Theory of Computing Systems, 66(4):861–909.
de Melo, A. A., Figueiredo, C. M. H., and Souza, U. S. (2020). A multivariate analysis of the strict terminal connection problem. Journal of Computer and System Sciences, 111:22–41.
de Oliveira Oliveira, M. (2013). Subgraphs satisfying MSO properties on z-topologically orderable digraphs. In Parameterized and Exact Computation, IPEC 2013, volume 8246 of Lecture Notes in Computer Science, pages 123–136.
Dourado, M. C., de Figueiredo, C. M. H., de Melo, A. A., de Oliveira Oliveira, M., and Souza, U. S. (2022). Computing the zig-zag number of directed graphs. Discrete Applied Mathematics, 312:86–105.
Dourado, M. C., Oliveira, R. A., Protti, F., and Souza, U. S. (2014). Design of connection networks with bounded number of non-terminal vertices. Matemática Contemporânea, 42(14):39–47.
Garey, M. R., Johnson, D. S., and Stockmeyer, L. J. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237–267.
Johnson, D. S. (1985). The NP-completeness column: An ongoing guide. Journal of Algorithms, 6(3):434–451.
Johnson, T., Robertson, N., Seymour, P. D., and Thomas, R. (2001). Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138–154.
Karp, R. M. (1972). Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA.
Kratochvíl, J., Masarík, T., and Novotná, J. (2020). U-bubble model for mixed unit interval graphs and its applications: The maxcut problem revisited. In 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, volume 170 of LIPIcs, pages 57:1–57:14.
Leibowitz, R., Assmann, S. F., and Peck, G. W. (1982). The interval count of a graph. SIAM Journal on Algebraic Discrete Methods, 3(4):485–494.
Müller, H. and Brandstädt, A. (1987). The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs. Theoretical Computer Science, 53(2-3):257–265.
White, K., Farber, M., and Pulleyblank, W. (1985). Steiner trees, connected domination and strongly chordal graphs. Networks, 15(1):109–124.
Publicado
06/08/2023
Como Citar
MELO, Alexsander A. de; FIGUEIREDO, Celina M. H. de; SOUZA, Uéverton S.; SILVA, Ana.
On (in)tractability of connection and cut problems. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 36. , 2023, João Pessoa/PB.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2023
.
p. 40-49.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2023.229754.
