5 papers
Co-Decompositions and FO Model Checking
Benjamin Merlin Bumpus, Guilherme C. M. Gomes, Laura Larios-Jones +1
Tree decompositions describe large graphs as gluings of smaller component parts. Here we study their categorical duals, tree co-decompositions, which construct large graphs via fib…
Revisiting the directed pathwidth of h-semicomplete digraphs
Guilherme C. M. Gomes, Raul Lopes, Matthias Mnich
A digraph is -semicomplete if every vertex has at most non-neighbors. In semicomplete digraphs, -triples are obstructions to bounded directed pathwidth with many algorith…
A more versatile model for enumerative kernelization: a case study for Vertex Cover
Marin Bougeret, Guilherme C. M. Gomes, Ignasi Sau
Enumerative kernelization is a recent promising at the intersection of parameterized complexity and enumeration algorithms, with two proposed models. The first, known as enum-kerne…
Revisiting Directed Disjoint Paths on tournaments (and relatives)
Guilherme C. M. Gomes, Raul Lopes, Ignasi Sau
In the Directed Disjoint Paths problem (-DDP), we are given a digraph pairs of terminals, and the goal is to find pairwise vertex-disjoint paths connecting each pair of…
Enumerating minimal dominating sets and variants in chordal bipartite graphs
Emanuel Castelo, Oscar Defrain, Guilherme C. M. Gomes
Enumerating minimal dominating sets with polynomial delay in bipartite graphs is a long-standing open problem. To date, even the subcase of chordal bipartite graphs is open, with t…