2 citations · 6 across the 22 of their papers we have counts for
13 papers · 1 filter
A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis
For a graph , the parameter treedepth measures the minimum depth among all forests , called elimination forests, such that is a subgraph of the ancestor-descendant closur…
Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
Michał Pilipczuk, Giannos Stamoulis, Michał Włodarczyk
In the Disjoint Shortest Paths problem one is given a graph and a set of vertex pairs. The question is whether there exist verte…
Faster diameter computation in graphs of bounded Euler genus
Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk +1
We show that for any fixed integer , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected -vert…
Minor Containment and Disjoint Paths in almost-linear time
Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis
We give an algorithm that, given graphs and , tests whether is a minor of in time ; here, is the number of vertices of and the ${\cal…
Computing paths of large rank in planar frameworks deterministically
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +1
A framework consists of an undirected graph and a matroid whose elements correspond to the vertices of . Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023]…
Shortest Cycles With Monotone Submodular Costs
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce the following submodular generalization of the Shortest Cycle problem. For a nonnegative monotone submodular cost function defined on the edges (or the vertices) o…
Faster parameterized algorithms for modification problems to minor-closed classes
Laure Morelle, Ignasi Sau, Giannos Stamoulis +1
Let be a minor-closed graph class and let be an -vertex graph. We say that is a -apex of if contains a set of at most vertices such…
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the…
Compound Logics for Modification Problems
Fedor V. Fomin, Petr A. Golovach, Ignasi Sau +2
We introduce a novel model-theoretic framework inspired from graph modification and based on the interplay between model theory and algorithmic graph minors. The core of our framew…
An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL
Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis +1
In general, a graph modification problem is defined by a graph modification operation and a target graph property . Typically, the modification operation $\bo…
k-apices of minor-closed graph classes. II. Parameterized algorithms
Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos
Let be a minor-closed graph class. We say that a graph is a -apex of if contains a set of at most vertices such that belongs…
Finding irrelevant vertices in linear time on bounded-genus graphs
Petr A. Golovach, Stavros G. Kolliopoulos, Giannos Stamoulis +1
The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these probl…
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos
For a finite collection of graphs , the \textsc{-TM-Deletion} problem has as input an -vertex graph and an integer and asks whether there exists a se…