5 papers · 1 filter
Parikh Automata on Finite and Infinite Words
Mario Grobler, Leif Sabellek, Sebastian Siebertz
We study Parikh automata on finite and infinite words. First we establish some results for Parikh automata on finite words. Following, we present several definitions of Parikh auto…
Elimination Distance to Dominated Clusters
Nicole Schirrmacher, Sebastian Siebertz, Alexandre Vigny
In the Dominated Cluster Deletion problem, we are given an undirected graph and integers and and the question is to decide whether there exists a set of at most ver…
On first-order transductions of classes of graphs
Samuel Braunfeld, Jaroslav NeÅ¡etÅil, Patrice Ossona de Mendez +1
We study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether o…
Flipper games for monadically stable graph classes
Jakub Gajarský, Nikolas Mählmann, Rose McCarty +6
A class of graphs is monadically stable if for any unary expansion of , one cannot interpret, in first-order logic, arbitrarily l…
Data reduction for directed feedback vertex set on graphs without long induced cycles
Jona Dirks, Enna Gerhard, Mario Grobler +2
We study reduction rules for Directed Feedback Vertex Set (DFVS) on directed graphs without long cycles. A DFVS instance without cycles longer than naturally corresponds to an…