5 papers · 1 filter
Enumeration kernels for Vertex Cover and Feedback Vertex Set
Marin Bougeret, Guilherme C. M. Gomes, Vinicius F. dos Santos +1
Enumerative kernelization is a recent and promising area sitting at the intersection of parameterized complexity and enumeration algorithms. Its study began with the paper of Creig…
Finding subdigraphs in digraphs of bounded directed treewidth
Raul Lopes, Ignasi Sau
It is well known that directed treewidth does not enjoy the nice algorithmic properties of its undirected counterpart. There exist, however, some positive results that, essentially…
A Parameterized Perspective on Uniquely Restricted Matchings
Juhi Chaudhary, Ignasi Sau, Meirav Zehavi
Given a graph G, a matching is a subset of edges of G that do not share an endpoint. A matching M is uniquely restricted if the subgraph induced by the endpoints of the edges of M…
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…
Computing distances is FPT on graph associahedra and W[2]-hard on hypergraphic polytopes
Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza +1
An elimination tree of a connected graph is a rooted tree on the vertices of obtained by choosing a root and recursing on the connected components of to obtain th…