Explanipedia

A practical algorithm for 3-admissibility Open

Patrick Greaves, Oded Lachish, Felix Reidl · 2025

The $3$-admissibility of a graph is a promising measure to identify real-world networks that have an algorithmically favourable structure. We design an algorithm that decides whether the $3$-admissibility of an input graph~$G$ is at most~$…

A practical algorithm for 2-admissibility Open

Christine Awofeso, Patrick Greaves, Oded Lachish, Felix Reidl · 2025

The $2$-admissibility of a graph is a promising measure to identify real-world networks which have an algorithmically favourable structure. In contrast to other related measures, like the weak/strong $2$-colouring numbers or the maximum de…

Correlation Clustering with Vertex Splitting Open

Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, Blair D. Sullivan · 2025

A Space-Efficient Algebraic Approach to Robotic Motion Planning Open

Matthias Bentert, Daniel Coimbra Salomao, Alex Crane, Yosuke Mizutani, Felix Reidl , et al. · 2024

We consider efficient route planning for robots in applications such as infrastructure inspection and automated surgical imaging. These tasks can be modeled via the combinatorial problem Graph Inspection. The best known algorithms for this…

Leveraging Fixed-Parameter Tractability for Robot Inspection Planning Open

Yosuke Mizutani, Daniel Coimbra Salomao, Alex Crane, Matthias Bentert, Pål Grønås Drange , et al. · 2024

Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, and medicine. Planning the paths for a robot to safely and e…

Correlation Clustering with Vertex Splitting Open

Matthias Bentert, Alex Crane, Pål Grønås Drange, Felix Reidl, Blair D. Sullivan · 2024

We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the face of uncertain information. We determine that both prob…

Computing Complexity Measures of Degenerate Graphs Open

Pål Grønås Drange, Patrick Greaves, Irene Muzi, Felix Reidl · 2023

We show that the VC-dimension of a graph can be computed in time n^{⌈log d+1⌉} d^{O(d)}, where d is the degeneracy of the input graph. The core idea of our algorithm is a data structure to efficiently query the number of vertices that see …

When you come at the kings you best not miss Open

Oded Lachish, Felix Reidl, Chhaya Trehan · 2022

A tournament is an orientation of a complete graph. We say that a vertex $x$ in a tournament $\vec T$ controls another vertex $y$ if there exists a directed path of length at most two from $x$ to $y$. A vertex is called a king if it contro…

Longitudinal Comparison of Constant Artifacts in Optical Coherence Tomography Angiography in Patients with Posterior Uveitis Compared to Healthy Subjects Open

Dominika Pohlmann, Martin Berlin, Felix Reidl, Steffen E. Künzel, Uwe Pleyer , et al. · 2022

Background: Knowledge about artifacts in optical coherence tomography angiography (OCTA) is important to avoid misinterpretations. An overview of possible artifacts in posterior uveitis provides important information for interpretations. M…

Meta-analysis of metagenomes via machine learning and assembly graphs reveals strain switches in Crohn’s disease Open

Taylor Reiter, Luiz Irber, Alicia A. Gingrich, Dylan Haynes, N. Tessa Pierce‐Ward , et al. · 2022

Microbial strains have closely related genomes but may have different phenotypes in the same environment. Shotgun metagenomic sequencing can capture the genomes of all strains present in a community but strain-resolved analysis from shotgu…

Kernelization and hardness of harmless sets in sparse classes Open

Pål Grønås Drange, Irene Muzi, Felix Reidl · 2021

In the classic TARGET SET SELECTION problem, we are asked to minimize the number of nodes to activate so that, after the application of a certain propagation process, all nodes of the graph are active. Bazgan and Chopin introduced the op…

Harmless Sets in Sparse Classes Open

Pål Grønås Drange, Irene Muzi, Felix Reidl · 2021

In the classic TARGET SAT SELECTION problem, we are asked to minimise the number of nodes to activate so that, after the application of a certain propagation process, all nodes of the graph are active. Bazgan and Chopin [Discrete Optimizat…

Exploring neighborhoods in large metagenome assembly graphs using spacegraphcats reveals hidden sequence diversity Open

C. Titus Brown, Dominik Moritz, Michael P. O’Brien, Felix Reidl, Taylor Reiter , et al. · 2020

A color-avoiding approach to subgraph counting in bounded expansion classes Open

Felix Reidl, Blair D. Sullivan · 2020

We present an algorithm to count the number of occurrences of a pattern graph $H$ as an induced subgraph in a host graph $G$. If $G$ belongs to a bounded expansion class, the algorithm runs in linear time. Our design choices are motivated …

A General Kernelization Technique for Domination and Independence Problems in Sparse Classes Open

Carl Einarson, Felix Reidl · 2020

We unify and extend previous kernelization techniques in sparse classes [Jochen Alber et al., 2004; Pilipczuk and Siebertz, 2018] by defining water lilies and show how they can be used in bounded expansion classes to construct linear biker…

Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness Open

Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz · 2019

The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. In this article…

Structural sparsity of complex networks: Bounded expansion in random models and real-world graphs Open

Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar , et al. · 2019

Longest paths in 2-edge-connected cubic graphs Open

Nikola K. Blanchard, Eldar Fischer, Oded Lachish, Felix Reidl · 2019

We prove almost tight bounds on the length of paths in $2$-edge-connected cubic graphs. Concretely, we show that (i) every $2$-edge-connected cubic graph of size $n$ has a path of length $Ω\left(\frac{\log^2{n}}{\log{\log{n}}}\right)$, and…

Alternative parameterizations of Metric Dimension Open

Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström · 2019

Hardness of FO Model-Checking on Random Graphs Open

Erik D. Demaine, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, Somnath Sikdar , et al. · 2019

It is known that FO model-checking is fixed-parameter tractable on Erdős - Rényi graphs G(n,p(n)) if the edge-probability p(n) is sufficiently small [Grohe, 2001] (p(n)=O(n^epsilon/n) for every epsilon>0). A natural question to ask is whet…

Domination Above r-Independence: Does Sparseness Help? Open

Carl Einarson, Felix Reidl · 2019

Inspired by the potential of improving tractability via gap- or above-guarantee parametrisations, we investigate the complexity of Dominating Set when given a suitable lower-bound witness. Concretely, we consider being provided with a maxi…

Path-contractions, edge deletions and connectivity preservation Open

Gregory Gutin, M. S. Ramanujan, Felix Reidl, Magnus Wahlström · 2018

Exploring neighborhoods in large metagenome assembly graphs reveals hidden sequence diversity Open

C. Titus Brown, Dominik Moritz, Michael P. O’Brien, Felix Reidl, Taylor Reiter , et al. · 2018

Genomes computationally inferred from large metagenomic data sets are often incomplete and may be missing functionally important content and strain variation. We introduce an information retrieval system for large metagenomic data sets tha…

Characterising bounded expansion by neighbourhood complexity Open

Felix Reidl, Fernando Sánchez Villaamil, Konstantinos S. Stavropoulos · 2018

Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming Open

Li-Hsuan Chen, Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil · 2018

Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility o…

Lower and Upper Bound for Computing the Size of All Second Neighbourhoods Open

Gregory Gutin, George B. Mertzios, Felix Reidl · 2018

We consider the problem of computing the size of each $r$-neighbourhood for every vertex of a graph. Specifically, we ask whether the size of the closed second neighbourhood can be computed in subquadratic time. Adapting the SETH reduction…

k-distinct in- and out-branchings in digraphs Open

Gregory Gutin, Felix Reidl, Magnus Wahlström · 2018

Empirical Evaluation of Approximation Algorithms for Generalized Graph\n Coloring and Uniform Quasi-Wideness Open

Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich, Felix Reidl, Sebastian Siebertz · 2018

The notions of bounded expansion and nowhere denseness not only offer robust\nand general definitions of uniform sparseness of graphs, they also describe the\ntractability boundary for several important algorithmic questions. In this\npape…

Parameterized Algorithms for Zero Extension and Metric Labelling\n Problems Open

Felix Reidl, Magnus Wahlström · 2018

We consider the problems ZERO EXTENSION and METRIC LABELLING under the\nparadigm of parameterized complexity. These are natural, well-studied problems\nwith important applications, but have previously not received much attention\nfrom para…

Searching for Maximum Out-Degree Vertices in Tournaments Open

Gregory Gutin, George B. Mertzios, Felix Reidl · 2018

A vertex $x$ in a tournament $T$ is called a king if for every vertex $y$ of $T$ there is a directed path from $x$ to $y$ of length at most 2. It is not hard to show that every vertex of maximum out-degree in a tournament is a king. Howeve…

Felix Reidl YOU? Author Swipe