Giannos Stamoulis

activity

20182026

most citedMinor Containment and Disjoint Paths in almost-linear time

2 citations · 6 across the 22 of their papers we have counts for

collaborators

29 papers

cs.LO2026

A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration

Nikolas Mählmann, Patrice {Ossona de Mendez}, Nicole Schirrmacher +4

We introduce \emph{sub-connectivity logic}, denoted by $FOscon$ , an extension of first-order logic for graphs with a specified set $Z$ of admissible edges. Its additional…

cs.LO2026

Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes

Ignasi Sau, Nicole Schirrmacher, Sebastian Siebertz +3

Algorithmic meta-theorems explain the tractability of large classes of computational problems by linking logical expressibility with structural graph properties. While extensions o…

cs.DS2025

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space

Benjamin Bergougnoux, Vera Chekan, Giannos Stamoulis

For a graph $G$ , the parameter treedepth measures the minimum depth among all forests $F$ , called elimination forests, such that $G$ is a subgraph of the ancestor-descendant closur…

math.CO2025

Catching Rats in $H$ -minor-free Graphs

Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos +1

We show that every $H$ -minor-free graph that also excludes a $(k \times k)$ -grid as a minor has treewidth/branchwidth bounded from above by a function $f (t, k)$ that is linear in $k…

cs.DS2025★ 1 cited

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 $G$ and a set $T = {(s_{1}, t_{1}), \dots, (s_{k}, t_{k})}$ of $k$ vertex pairs. The question is whether there exist verte…

cs.LO2025

Low rank MSO

Mikołaj Bojańczyk, Michał Pilipczuk, Wojciech Przybyszewski +2

We introduce a new logic for describing properties of graphs, which we call low rank MSO. This is the fragment of monadic second-order logic in which set quantification is restrict…

cs.DS2025

Faster diameter computation in graphs of bounded Euler genus

Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk +1

We show that for any fixed integer $k \geq 0$ , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected $n$ -vert…

math.CO2024

Generating strongly 2-connected digraphs

Meike Hatzel, Stephan Kreutzer, Evangelos Protopapas +3

We prove that there exist four operations such that given any two strongly $2$ -connected digraphs $H$ and $D$ where $H$ is a butterfly-minor of $D$ , there exists a sequence $D_0,\d…

cs.LO2024

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Given a graph $G$ and a vertex set $X$ , the annotated treewidth tw $(G, X)$ of $X$ in $G$ is the maximum treewidth of an $X$ -rooted minor of $G$ , i.e., a minor $H$ where the model of…

cs.DS2024★ 2 cited

Minor Containment and Disjoint Paths in almost-linear time

Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis

We give an algorithm that, given graphs $G$ and $H$ , tests whether $H$ is a minor of $G$ in time $O_{H} (n^{1 + o (1)})$ ; here, $n$ is the number of vertices of $G$ and the ${\cal…

cs.LO2024

Elementary first-order model checking for sparse graphs

Jakub Gajarský, Michał Pilipczuk, Marek Sokołowski +2

It is known that for subgraph-closed graph classes the first-order model checking problem is fixed-parameter tractable if and only if the class is nowhere dense [Grohe, Kreutzer, S…

math.CO2023

Branchwidth is (1,g)-self-dual

Georgios Kontogeorgiou, Alexandros Leivaditis, Kostas I. Psaromiligkos +2

A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. We prove that the b…

cs.DS2023

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 $G$ and a matroid $M$ whose elements correspond to the vertices of $G$ . Recently, Fomin et al. [SODA 2023] and Eiben et al. [ArXiV 2023]…

cs.LO2023

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes

Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis +2

Disjoint-paths logic, denoted $FO$ + $dp$ , extends first-order logic ( $FO$ ) with atomic predicates $dp_{r} [(x_{1}, y_{1}), \dots, (x_{r}, y_{r})]$ , expressing…

cs.DS2022

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 $f$ defined on the edges (or the vertices) o…

cs.LO2022

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos

The disjoint paths logic, FOL+DP, is an extension of First-Order Logic (FOL) with the extra atomic predicate $dp_{k} (x_{1}, y_{1}, \dots, x_{k}, y_{k}),$ expressing the existence of in…

cs.DS2022★ 2 cited

Faster parameterized algorithms for modification problems to minor-closed classes

Laure Morelle, Ignasi Sau, Giannos Stamoulis +1

Let $G$ be a minor-closed graph class and let $G$ be an $n$ -vertex graph. We say that $G$ is a $k$ -apex of $G$ if $G$ contains a set $S$ of at most $k$ vertices such…

cs.DS2022

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…

math.CO2022

Combing a Linkage in an Annulus

Petr A. Golovach, Giannos Stamoulis, Dimitrios M. Thilikos

A linkage in a graph $G$ of size $k$ is a subgraph $L$ of $G$ whose connected components are $k$ paths. The pattern of a linkage of size $k$ is the set of $k$ pairs formed by the e…

cs.DS2021

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…

cs.DS2021

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 $P$ . Typically, the modification operation $\bo…

cs.DM2021

Block Elimination Distance

Öznur Yaşar Diner, Archontia C. Giannopoulou, Giannos Stamoulis +1

We introduce the block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class $G$ , the class ${\cal B}({\cal…

math.CO2021★ 1 cited

k-apices of minor-closed graph classes. I. Bounding the obstructions

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

Let $G$ be a minor-closed graph class. We say that a graph $G$ is a $k$ -apex of $G$ if $G$ contains a set $S$ of at most $k$ vertices such that $G ∖ S$ b…

cs.DM2021

A more accurate view of the Flat Wall Theorem

Ignasi Sau, Giannos Stamoulis, Dimitrios M. Thilikos

We introduce a supporting combinatorial framework for the Flat Wall Theorem. In particular, we suggest two variants of the theorem and we introduce a new, more versatile, concept o…

A Logic for Minor-Free Graph Classes: Model Checking, Dependence, and Combinatorial Reconfiguration

Model Checking for Low Monodimensionality Fragments of CMSO on Topological-Minor-Free Graph Classes

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space

Catching Rats in H-minor-free Graphs

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable

Low rank MSO

Faster diameter computation in graphs of bounded Euler genus

Generating strongly 2-connected digraphs

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes

Minor Containment and Disjoint Paths in almost-linear time

Elementary first-order model checking for sparse graphs

Branchwidth is (1,g)-self-dual

Computing paths of large rank in planar frameworks deterministically

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes

Shortest Cycles With Monotone Submodular Costs

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

Faster parameterized algorithms for modification problems to minor-closed classes

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

Combing a Linkage in an Annulus

Compound Logics for Modification Problems

An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL

Block Elimination Distance

k-apices of minor-closed graph classes. I. Bounding the obstructions

A more accurate view of the Flat Wall Theorem

Catching Rats in $H$ -minor-free Graphs