1 citations · 1 across the 10 of their papers we have counts for
12 papers
Orienting mixed graphs for reachability pairs: When the all pairs setting is easier than the general one
Florian Hörsch, Marta Piecyk, Krisztina Szilágyi
Given a mixed graph and an ordered pair of vertices in , we say that an orientation of satisfies if is reachable from in .…
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…
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor Antić, Jiří Fiala, Jelena Glišić +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller than t…
A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
Thekla Hamm, Sukanya Pandey, Krisztina Szilágyi
Given a planar graph, a subset of its vertices called terminals, and , the Face Cover Number problem asks whether the terminals lie on the boundaries of at most $…
Pathfinding in Self-Deleting Graphs
Michal Dvořák, Dušan Knop, Michal Opler +3
In this paper, we study the problem of pathfinding on traversal-dependent graphs, i.e., graphs whose edges change depending on the previously visited vertices. In particular, we st…
Density of Traceable Graphs
Michal Dvořák, Dušan Knop, Michal Opler +3
We establish tight lower and upper bounds on the number of edges in traceable graphs in several classes of dense graphs. A graph is traceable if it has a Hamiltonian path. We show…
Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
Narek Bojikian, Alexander Firbas, Robert Ganian +2
We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph and a constraint function , we ask for a (minimu…
XALP-completeness of Parameterized Problems on Planar Graphs
Hans L. Bodlaender, Krisztina Szilágyi
The class XNLP consists of (parameterized) problems that can be solved nondeterministically in time and space, where is the size of the input instan…
Parameterized Algorithms for Covering by Arithmetic Progressions
Ivan Bliznets, Jesper Nederlof, Krisztina Szilágyi
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two pro…
Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
Jesper Nederlof, Krisztina Szilágyi
In this paper we investigate the parameterized complexity of the task of counting and detecting occurrences of small patterns in unit disk graphs: Given an -vertex unit disk gra…
Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
Carla Groenland, Jesper Nederlof, Isja Mannens +1
We study the fine-grained complexity of counting the number of colorings and connected spanning edge sets parameterized by the cutwidth and treewidth of the graph. While decomposit…
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
Isja Mannens, Jesper Nederlof, Céline Swennenhuis +1
We study a variant of Min Cost Flow in which the flow needs to be connected. Specifically, in the Connected Flow problem one is given a directed graph , along with a set of dema…