13 citations · 48 across the 26 of their papers we have counts for
26 papers · 1 filter
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…
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…
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…
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…
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…
Path-contractions, edge deletions and connectivity preservation
Gregory Gutin, M. S. Ramanujan, Felix Reidl +1
We study several problems related to graph modification problems under connectivity constraints from the perspective of parameterized complexity: {\sc (Weighted) Biconnectivity Del…
-Distinct In- and Out-Branchings in Digraphs
Gregory Gutin, Felix Reidl, Magnus Wahlström
An out-branching and an in-branching of a digraph are called -distinct if each of them has arcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that…
Fast Biclustering by Dual Parameterization
Pål Grønås Drange, Felix Reidl, Fernando Sánchez Villaamil +1
We study two clustering problems, Starforest Editing, the problem of adding and deleting edges to obtain a disjoint union of stars, and the generalization Bicluster Editing. We sho…
Kernelization and Sparseness: the case of Dominating Set
Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin +9
We prove that for every positive integer and for every graph class of bounded expansion, the -Dominating Set problem admits a linear kernel on graphs from $\mat…
A Faster Parameterized Algorithm for Treedepth
Felix Reidl, Peter Rossmanith, Fernando Sanchez Villaamil +1
The width measure \emph{treedepth}, also known as vertex ranking, centered coloring and elimination tree height, is a well-established notion which has recently seen a resurgence o…
Kernelization Using Structural Parameters on Sparse Graph Classes
Jakub Gajarský, Petr Hliněný, Jan Obdržálek +5
Meta-theorems for polynomial (linear) kernels have been the subject of intensive research in parameterized complexity. Heretofore, meta-theorems for linear kernels exist on graphs…