13 citations · 48 across the 26 of their papers we have counts for
39 papers
A characterization of one-sided error testable graph properties in bounded degeneracy graphs
Oded Lachish, Amit Levi, Ilan Newman +1
We consider graph property testing in -degenerate graphs under the random neighbor oracle model (Czumaj and Sohler, FOCS 2019). In this framework, a tester explores a graph by s…
A practical algorithm for 3-admissibility
Christine Awofeso, Patrick Greaves, Oded Lachish +1
The -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 wheth…
Efficient Trace Frequency Queries in Sparse Graphs
Christine Awofeso, Pål Grønås Drange, Patrick Greaves +2
Understanding how a vertex relates to a set of vertices is a fundamental task in graph analysis. Given a graph and a vertex set , consider the collection of s…
A sufficient condition for characterizing the one-sided testable properties of families of graphs in the Random Neighbour Oracle Model
Christine Awofeso, Patrick Greaves, Oded Lachish +2
We study property testing in the \emph{random neighbor oracle} model for graphs, originally introduced by Czumaj and Sohler [STOC 2019]. Specifically, we initiate the study of char…
Counting large patterns in degenerate graphs
Christine Awofeso, Patrick Greaves, Oded Lachish +1
The problem of subgraph counting asks for the number of occurrences of a pattern graph as a subgraph of a host graph and is known to be computationally challenging: it is $…
A practical algorithm for 2-admissibility
Christine Awofeso, Patrick Greaves, Oded Lachish +1
The -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, l…
A Space-Efficient Algebraic Approach to Robotic Motion Planning
Matthias Bentert, Daniel Coimbra Salomao, Alex Crane +3
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 p…
Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
Yosuke Mizutani, Daniel Coimbra Salomao, Alex Crane +5
Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, a…
Correlation Clustering with Vertex Splitting
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the…
Computing complexity measures of degenerate graphs
Pål Grønås Drange, Patrick Greaves, Irene Muzi +1
We show that the VC-dimension of a graph can be computed in time , where is the degeneracy of the input graph. The core idea of our algorithm is a data s…
When you come at the kings you best not miss
Oded Lachish, Felix Reidl, Chhaya Trehan
A tournament is an orientation of a complete graph. We say that a vertex in a tournament controls another vertex if there exists a directed path of length at most…
Harmless Sets in Sparse Classes
Pål Grønås Drange, Irene Muzi, Felix Reidl
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…
A general kernelization technique for domination and independence problems in sparse classes
Carl Einarson, Felix Reidl
We unify and extend previous kernelization techniques in sparse classes [6,17] by defining water lilies and show how they can be used in bounded expansion classes to construct line…
A color-avoiding approach to subgraph counting in bounded expansion classes
Felix Reidl, Blair D. Sullivan
We present an algorithm to count the number of occurrences of a pattern graph as an induced subgraph in a host graph . If belongs to a bounded expansion class, the algor…
Domination above r-independence: does sparseness help?
Carl Einarson, Felix Reidl
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…
Longest paths in 2-edge-connected cubic graphs
Nikola K. Blanchard, Eldar Fischer, Oded Lachish +1
We prove almost tight bounds on the length of paths in -edge-connected cubic graphs. Concretely, we show that (i) every -edge-connected cubic graph of size has a path of…
Lower and Upper Bound for Computing the Size of All Second Neighbourhoods
Gregory Gutin, George B. Mertzios, Felix Reidl
We consider the problem of computing the size of each -neighbourhood for every vertex of a graph. Specifically, we ask whether the size of the closed second neighbourhood can be…
Alternative parameterizations of Metric Dimension
Gregory Gutin, M. S. Ramanujan, Felix Reidl +1
A set of vertices in a graph is called resolving if for any two distinct , there is such that , where ${\rm di…
Parameterized Algorithms for Zero Extension and Metric Labelling Problems
Felix Reidl, Magnus Wahlström
We consider the problems ZERO EXTENSION and METRIC LABELLING under the paradigm of parameterized complexity. These are natural, well-studied problems with important applications, b…
Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
Wojciech Nadara, Marcin Pilipczuk, Roman Rabinovich +2
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 f…
Searching for Maximum Out-Degree Vertices in Tournaments
Gregory Gutin, George B. Mertzios, Felix Reidl
A vertex in a tournament is called a king if for every vertex of there is a directed path from to of length at most 2. It is not hard to show that every ver…
A practical fpt algorithm for Flow Decomposition and transcript assembly
Kyle Kloster, Philipp Kuinke, Michael P. O'Brien +4
The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transc…
Designing Deterministic Polynomial-Space Algorithms by Color-Coding Multivariate Polynomials
Gregory Gutin, Felix Reidl, Magnus Wahlström +1
In recent years, several powerful techniques have been developed to design {\em randomized} polynomial-space parameterized algorithms. In this paper, we introduce an enhancement of…
Being even slightly shallow makes life hard
Irene Muzi, Michael P. O'Brien, Felix Reidl +1
We study the computational complexity of identifying dense substructures, namely -shallow topological minors and -subdivisions. Of particular interest is the case when $r=1…