-
Chapter and Conference Paper
Correction to: Parameterized Algorithms for Covering by Arithmetic Progressions
-
Chapter and Conference Paper
Algorithms and Turing Kernels for Detecting and Counting Small Patterns in Unit Disk Graphs
In this paper we investigate the parameterized complexity of the task of counting and detecting occurrences of small patterns in unit disk graphs: Given an n-vertex unit disk graph G with an embedding of ply p (t...
-
Chapter and Conference Paper
Exact and Parameterized Algorithms for Choosability
In the Choosability problem (or list chromatic number problem), for a given graph G, we need to find the smallest k such that G admits a list coloring for any list assignment where all lists contain at least k co...
-
Chapter and Conference Paper
Parameterized Algorithms for Covering by Arithmetic Progressions
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic prog...
-
Article
Open AccessOn the Fine-grained Parameterized Complexity of Partial Scheduling to Minimize the Makespan
We study a natural variant of scheduling that we call partial scheduling: in this variant an instance of a scheduling problem along with an integer k is given and one seeks an optimal schedule where not all, but ...
-
Chapter and Conference Paper
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
We study a variant of Min Cost Flow in which the flow needs to be connected. Specifically, in the Connected Flow problem one is given a directed graph G, along with a set of demand vertices
-
Chapter
Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
We survey a number of recent results that relate the fine-grained complexity of several NP-Hard problems with the rank of certain matrices. The main technical theme is that for a wide variety of Divide & Conqu...
-
Chapter and Conference Paper
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
For many algorithmic problems on graphs of treewidth \(t\) t , a standard dy...
-
Article
Open AccessNew Tools and Connections for Exponential-Time Approximation
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer ...
-
Chapter and Conference Paper
Hamiltonicity Below Dirac’s Condition
Dirac’s theorem (1952) is a classical result of graph theory, stating that an n-vertex graph ( \(n \ge 3\) ) is Hamilto...
-
Chapter and Conference Paper
On Directed Feedback Vertex Set Parameterized by Treewidth
We study the Directed Feedback Vertex Set problem parameterized by the treewidth of the input graph. We prove that unless the Exponential Time Hypothesis fails, the problem cannot be solved in time ...
-
Reference Work Entry In depth
Exact Algorithms and Time/Space Tradeoffs
-
Article
Minimizing Rosenthal Potential in Multicast Games
A multicast game is a network design game modelling how selfish non-cooperative agents build and maintain one-to-many network communication. There is a special source node and a collection of agents located at...
-
Article
Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of Algorithms for Steiner Tree on Tree Decompositions
Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al. (Proceedings of the 40th in...
-
Living Reference Work Entry In depth
Exact Algorithms and Time/Space Tradeoffs
-
Chapter and Conference Paper
Subexponential Time Algorithms for Finding Small Tree and Path Decompositions
The Minimum Size Tree Decomposition (MSTD) and Minimum Size Path Decomposition (MSPD) problems ask for a given n-vertex graph G and integer k, what is the minimum number of bags of a tree decomposition (respectiv...
-
Article
Inclusion/Exclusion Meets Measure and Conquer
Inclusion/exclusion and measure and conquer are two central techniques from the field of exact exponential-time algorithms that recently received a lot of attention. In this paper, we show that both techniques...
-
Article
Open AccessFast Polynomial-Space Algorithms Using Inclusion-Exclusion
Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in $\math...
-
Chapter and Conference Paper
Speeding Up Dynamic Programming with Representative Sets
Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al. [5], it was shown that for ...
-
Chapter and Conference Paper
Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
It is well known that many local graph problems, like Vertex Cover and Dominating Set, can be solved in $2^{\mathcal{O}(\mathtt{tw})}n...
