Data: 15/07/2021, às 16:00 horas (GMT-3, horário de Brasília).
Título: Reconfiguration of Connected Graph Partitions via Recombination
Palestrante: Hugo Akitaya (University of Massachusetts Lowell)


Resumo: Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V(G) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k-Partition with slack s, denoted (k,s)-BCP, is a partition of V(G) into k nonempty subsets, of sizes n1,…,nk with |ni−n/k|≤s, each of which induces a connected subgraph (when s=0, the k parts are perfectly balanced, and we call it k-BCP for short).

A recombination is an operation that takes a (k,s)-BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s≥0, we wish to determine whether there exists a sequence of recombinations that transform A into B via (k,s)-BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6(k−1) recombinations. (2) If G is Hamiltonian, the transformation is possible using O(kn) recombinations for any s≥n/k, and (3) we provide negative instances for s≤n/(3k). (4) We show that the problem is PSPACE-complete when k∈O(nε) and s∈O(n1−ε), for any constant 0<ε≤1, even for restricted settings such as when G is an edge-maximal planar graph or when k=3 and G is planar.