Mario Grobler

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2026

Towards Settling the Complexity of the Lettericity Problem

Mario Grobler, Nils Morawietz, Silas Cato Sacher

The lettericity of a graph $G = (V, E)$ is defined as the smallest size of an alphabet $I^£$ such that there is a word $w_{1} \dots w_{∣ V ∣} \in I^£^{*}$ and a decoder $\mathcal{D} \subseteq…

cs.DS2025

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 $d$ naturally corresponds to an…

cs.DS2024

Kernelization Complexity of Solution Discovery Problems

Mario Grobler, Stephanie Maaz, Amer E. Mouawad +3

In the solution discovery variant of a vertex (edge) subset problem $I^$ on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph $G$ to…