Complexidade parametrizada do problema de reconfiguração de separadores

  • Guilherme de C. M. Gomes UFMG
  • Vinicius F. dos Santos UFMG

Resumo


Separadores em grafos são conjuntos de vértices cuja remoção destrói todos os caminhos entre dois vértices dados. Em particular, dizemos que um conjunto é um st-separador se sua remoção destrói todos os caminhos entre dois vértices s e t. Problemas de reconfiguração recebem como entrada dois objetos combinatórios e o objetivo é transformar um no outro, mantendo certas propriedades ao longo da transformação. No problema de reconfiguração de separadores, são dados um grafo G e dois st-separadores A e B e deseja-se transformar A em B utilizando certas operações de modificação, de maneira que todos os passos intermediários sejam, também, st-separadores. Este problema é NP-dificil e, em algumas versões, é PSPACE-dificil. Neste trabalho, consideramos pela primeira vez a complexidade parametrizada deste problema de reconfiguração e mostramos resultados positivos para uma parametrização estrutural, além de discutir outras parametrizações naturais.

Referências

Bonamy M, Bousquet N (2014) Reconfiguring independent sets in cographs. arXiv preprint arXiv:14061433

Bonamy M, Johnson M, Lignos I, Patel V, Paulusma D (2012) Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs. Journal of Combinatorial Optimization 27(1):132–143

Bonsma P, Cereceda L (2007) Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Lecture Notes in Computer Science p 738–749

Cereceda L, van den Heuvel J, Johnson M (2011) Finding paths between 3-colorings. J Graph Theory 67(1):69–82

Demaine ED, Demaine ML, Fox-Epstein E, Hoang DA, Ito T, Ono H, Otachi Y, Uehara R, Yamada T (2015) Linear-time algorithm for sliding tokens on trees. Theoretical Computer Science 600:132 – 142

Gharibian S, Sikora J (2015) Ground state connectivity of local hamiltonians. In: Halldórsson MM, Iwama K, Kobayashi N, Speckmann B (eds) Automata, Languages, and Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 617–628

Gomes G, Nogueira SH, Santos VFd (2020) Some results on vertex separator reconfiguration. arXiv preprint arXiv:200410873

Gopalan P, Kolaitis PG, Maneva EN, Papadimitriou CH (2006) The connectivity of boolean satisfiability: Computational and structural dichotomies. In: Bugliesi M, Preneel B, Sassone V, Wegener I (eds) Automata, Languages and Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 346–357

Hearn RA, Demaine ED (2005) PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science 343(1-2):72–96

Ito T, Demaine ED, Harvey NJ, Papadimitriou CH, Sideri M, Uehara R, Uno Y (2011) On the complexity of reconfiguration problems. Theoretical Computer Science 412(12):1054 – 1065

Ito T, Kamiński M, Ono H, Suzuki A, Uehara R, Yamanaka K (2014) On the parameterized complexity for token jumping on graphs. Theory and Applications of Models of Computation p 341–351

Ito T, Ono H, Otachi Y (2015) Reconfiguration of cliques in a graph. In: Jain R, Jain S, Stephan F (eds) Theory and Applications of Models of Computation, Springer International Publishing, Cham, pp 212–223

Johnson WW, Story WE (1879) Notes on the "15"puzzle. American Journal of Mathematics 2(4):397–404

Kanj I, Xia G (2015) Flip distance is in FPT time O(n + k · ck). In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

Lokshtanov D, Mouawad AE (2018) The complexity of independent set reconfiguration on bipartite graphs. ACM Trans Algorithms 15(1), DOI 10.1145/3280825

Lubiw A, Pathak V (2015) Flip distance between two triangulations of a point set is NP-complete. Computational Geometry 49:17 – 23, 24th Canadian Conference on Computational Geometry (CCCG’12)

Makino K, Tamaki S, Yamamoto M (2011) An exact algorithm for the boolean connectivity problem for k-CNF. Theoretical Computer Science 412(35):4613–4618

Mouawad AE, Nishimura N, Raman V, Wrochna M (2014) Reconfiguration over tree decompositions. Lecture Notes in Computer Science p 246–257

Mouawad AE, Nishimura N, Raman V, Simjour N, Suzuki A (2016) On the parameterized complexity of reconfiguration problems. Algorithmica 78(1):274–297
Publicado
06/08/2023
GOMES, Guilherme de C. M.; SANTOS, Vinicius F. dos. Complexidade parametrizada do problema de reconfiguração de separadores. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 79-83. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230681.