Complexidade parametrizada do problema de reconfiguração de separadores
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, 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
