Author

R. Ganian

h-index 26 View on Semantic Scholar

We have 6 of 175 papers

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Oct 2026

A Uniform Algorithm for Strict NP on Bounded-Treedepth Graphs

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; however, this provides neither a procedure for constructing these algorithms nor computable bounds on their parameter dependence. We turn thi...

Thomas Depian, Robert Ganian, Jakob Greilhuber et al. · 0 citations

Jul 2026

A Fixed-Parameter Algorithm for Extending Upward Planar Drawings

A fixed-parameter algorithm for extending upward planar drawings is presented which overcomes this drawback by using the $\textit{vertex+edge deletion distance}$ as the parameter, thus achieving tractability even for instances with many missing edges.

V. Chekan, Robert Ganian, Viktoriia Korchemna · arXiv.org · 0 citations

Preprint Aug 2026

The (Parameterized) Complexity of Ordering a Graph While Avoiding a Forbidden Pattern

It is shown that Pattern Avoidance is $\Sigma_2^{\textsf{P}}$-complete and furthermore remains intractable (in both the classical and parameterized sense) even under a variety of severe restrictions to both the pattern $P$ and the graph $G$.

Thomas Depian, S. D. Fink, Alexander Firbas et al. · 0 citations

Jul 2026

Two-Layer Drawings with a Tree on Top: Vertex Splits and Fixed-Parameter Algorithms

This paper investigates the parameterized complexity of this problem and obtains an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot k})$ algorithms.

Alexander Firbas, R. Ganian, Sylvain Meunier et al. · arXiv.org · 0 citations

Preprint Aug 2026

Not All Degree Constraints Are Created Equal when Computing Spanning Trees

This paper proves that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph, and shows that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number.

Narek Bojikian, Alexander Firbas, Robert Ganian et al. · 0 citations

Jul 2026

Improved Learning with Structure: Fine-Grained Complexity of Minimum Consistent Subset

A comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs is developed and the results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.

R. Ganian, M. Vasilakis, Simon Wietheger · arXiv.org · 0 citations