7 papers
Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes
Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz +3
Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions o…
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…
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…
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…