24 citations · 124 across the 75 of their papers we have counts for
57 papers · 1 filter
Solving SAT via Treewidth Backdoors in Linear Time: Beyond Sparsity
Jan Dreier, Robert Ganian, Marlene Gründel +2
The Boolean Satisfiability (SAT) problem is a remarkably expressive computational problem, serving both as a cornerstone of complexity theory and as a unifying language for a wide…
Ramsey Meets Simultaneous Planarity: Vertex Integrity and Pathwidth
Thomas Depian, Simon D. Fink, Alexander Firbas +3
We study the following simultaneous embedding problem: Given k graphs on the same vertex set with the same pairwise intersection, do they admit planar drawings that coincide on the…
A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs
Thomas Depian, Robert Ganian, Jakob Greilhuber +2
A classical well-quasi-ordering result guarantees the existence of non-uniform linear-time algorithms for all problems in Strict NP on relational structures of bounded treedepth; h…
The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern
Thomas Depian, Simon D. Fink, Alexander Firbas +3
In this paper, we study the Pattern Avoidance problem of determining whether a given graph admits a linear vertex order which avoids a given pattern , i.e., a vertex sequenc…
Not All Degree Constraints Are Created Equal when Computing Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share…
Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset
Robert Ganian, Manolis Vasilakis, Simon Wietheger
Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretica…