research
∙
04/28/2023
Structural Parameterizations for Two Bounded Degree Problems Revisited
We revisit two well-studied problems, Bounded Degree Vertex Deletion and...
share
research
∙
02/19/2023
Parameterized Max Min Feedback Vertex Set
Given a graph G and an integer k, Max Min FVS asks whether there exists ...
research
∙
10/18/2022
First Order Logic on Pathwidth Revisited Again
Courcelle's celebrated theorem states that all MSO-expressible propertie...
research
∙
02/14/2022
Hedonic Games and Treewidth Revisited
We revisit the complexity of the well-studied notion of Additively Separ...
research
∙
09/23/2021
Filling Crosswords is Very Hard
We revisit a classical crossword filling puzzle which already appeared i...
research
∙
09/21/2021
Fine-grained Meta-Theorems for Vertex Integrity
Vertex Integrity is a graph measure which sits squarely between two more...
research
∙
04/27/2021
Minimum Stable Cut and Treewidth
A stable cut of a graph is a cut whose weight cannot be increased by cha...
research
∙
03/30/2021
Determining a Slater Winner is Complete for Parallel Access to NP
We consider the complexity of deciding the winner of an election under t...
research
∙
01/19/2021
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-Exponential Approximation
An upper dominating set is a minimal dominating set in a graph. In the U...
research
∙
10/13/2020
Digraph Coloring and Distance to Acyclicity
In k-Digraph Coloring we are given a digraph and are asked to partition ...
research
∙
09/21/2020
(In)approximability of Maximum Minimal FVS
We study the approximability of the NP-complete Maximum Minimal Feedback...
research
∙
08/17/2020
Grundy Distinguishes Treewidth from Pathwidth
Structural graph parameters, such as treewidth, pathwidth, and clique-wi...
research
∙
08/08/2020
Parameterized Complexity of (A,ℓ)-Path Packing
Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Pac...
research
∙
11/20/2019
New Algorithms for Mixed Dominating Set
A mixed dominating set is a collection of vertices and edges that domina...
research
∙
10/12/2019
Improved (In-)Approximability Bounds for d-Scattered Set
In the d-Scattered Set problem we are asked to select at least k vertice...
research
∙
05/01/2019
Independent Set Reconfiguration Parameterized by Modular-Width
Independent Set Reconfiguration is one of the most well-studied problems...
research
∙
02/13/2019
New Results on Directed Edge Dominating Set
We study a family of generalizations of Edge Dominating Set on directed ...
research
∙
01/27/2019
Parameterized Complexity of Safe Set
In this paper we study the problem of finding a small safe set S in a gr...
research
∙
10/25/2018
Maximum Independent Sets in Subcubic Graphs: New Results
The maximum independent set problem is known to be NP-hard in the class ...
research
∙
07/30/2018
Parameterized Orientable Deletion
A graph is d-orientable if its edges can be oriented so that the maximum...
research
∙
07/14/2018
Token Sliding on Split Graphs
We show that the independent set reconfiguration problem on split graphs...
research
∙
05/22/2018
QBF as an Alternative to Courcelle's Theorem
We propose reductions to quantified Boolean formulas (QBF) as a new appr...
research
∙
04/23/2018
How Bad is the Freedom to Flood-It?
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs th...
research
∙
04/21/2018
Finer Tight Bounds for Coloring on Clique-Width
We revisit the complexity of the classical k-Coloring problem parameteri...
research
∙
01/31/2018
Parameterized Power Vertex Cover
We study a recently introduced generalization of the Vertex Cover (VC) p...
research
∙
01/11/2018
Parameterized (Approximate) Defective Coloring
In Defective Coloring we are given a graph G = (V, E) and two integers χ...
research
∙
10/02/2017
On the Parameterized Complexity of Red-Blue Points Separation
We study the following geometric separation problem: Given a set R of ...
research
∙
09/07/2017