
Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin,
M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on
graphs of bounded genus and Hminorfree graphs, J. ACM, 52 (2005),
pp.866893] as a tool to obtain subexponential time parameterized algorithms
on Hminorfree graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality:
new connections between FPT algorithms and PTASs, in Proceedings of the 16th
Annual ACMSIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005,
pp.590601] this theory was extended in order to obtain polynomial time
approximation schemes (PTASs) for bidimensional problems. In this work, we
establish a third metaalgorithmic direction for bidimensionality theory by
relating it to the existence of linear kernels for parameterized problems. In
particular, we prove that every minor (respectively contraction) bidimensional
problem that satisfies a separation property and is expressible in Countable
Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs
that exclude a fixed graph (respectively an apex graph) H as a minor. Our
results imply that a multitude of bidimensional problems g graph classes. For
most of these problems no polynomial kernels on Hminorfree graphs were known
prior to our work.

In the classic Integer Programming (IP) problem, the objective is to decide
whether, for a given $m \times n$ matrix $A$ and an $m$vector $b=(b_1,\dots,
b_m)$, there is a nonnegative integer $n$vector $x$ such that $Ax=b$. Solving
(IP) is an important step in numerous algorithms and it is important to obtain
an understanding of the precise complexity of this problem as a function of
natural parameters of the input.
The classic pseudopolynomial time algorithm of Papadimitriou [J. ACM 1981]
for instances of (IP) with a constant number of constraints was only recently
improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder
[ArXiv 2018]. We continue this line of work and show that under the Exponential
Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal.
We also show that when the matrix $A$ is assumed to be nonnegative, a
component of Papadimitriou's original algorithm is already nearly optimal under
ETH.
This motivates us to pick up the line of research initiated by Cunningham and
Geelen [IPCO 2007] who studied the complexity of solving (IP) with nonnegative
matrices in which the number of constraints may be unbounded, but the
branchwidth of the columnmatroid corresponding to the constraint matrix is a
constant. We prove a lower bound on the complexity of solving (IP) for such
instances and obtain optimal results with respect to a closely related
parameter, pathwidth. Specifically, we prove matching upper and lower bounds
for (IP) when the pathwidth of the corresponding columnmatroid is a constant.

An input to the Popular Matching problem, in the roommates setting, consists
of a graph $G$ and each vertex ranks its neighbors in strict order, known as
its preference. In the Popular Matching problem the objective is to test
whether there exists a matching $M^\star$ such that there is no matching $M$
where more people are happier with $M$ than with $M^\star$. In this paper we
settle the computational complexity of the Popular Matching problem in the
roommates setting by showing that the problem is NPcomplete. Thus, we resolve
an open question that has been repeatedly, explicitly asked over the last
decade.

Given a directed graph $D$ on $n$ vertices and a positive integer $k$, the
ArcDisjoint Cycle Packing problem is to determine whether $D$ has $k$
arcdisjoint cycles. This problem is known to be W[1]hard in general directed
graphs. In this paper, we initiate a systematic study on the parameterized
complexity of the problem restricted to tournaments. We show that the problem
is fixedparameter tractable and admits a polynomial kernel when parameterized
by the solution size $k$. In particular, we show that it can be solved in
$2^{\mathcal{O}(k \log k)} n^{\mathcal{O}(1)}$ time and has a kernel with
$\mathcal{O}(k)$ vertices. The primary ingredient in both these results is a
minmax theorem that states that every tournament either contains $k$
arcdisjoint triangles or has a feedback arc set of size at most $6k$. Our
belief is that this combinatorial result is of independent interest and could
be useful in other problems related to cycles in tournaments.

Given a Counting Monadic Second Order (CMSO) sentence $\psi$, the
CMSO$[\psi]$ problem is defined as follows. The input to CMSO$[\psi]$ is a
graph $G$, and the objective is to determine whether $G\models \psi$. Our main
theorem states that for every CMSO sentence $\psi$, if CMSO$[\psi]$ is solvable
in polynomial time on "globally highly connected graphs", then CMSO$[\psi]$ is
solvable in polynomial time (on general graphs). We demonstrate the utility of
our theorem in the design of parameterized algorithms. Specifically we show
that technical problemspecific ingredients of a powerful method for designing
parameterized algorithms, recursive understanding, can be replaced by a
blackbox invocation of our main theorem. We also show that our theorem can be
easily deployed to show fixed parameterized tractability of a wide range of
problems, where the input is a graph $G$ and the task is to find a connected
induced subgraph of $G$ such that "few" vertices in this subgraph have
neighbors outside the subgraph, and additionally the subgraph has a
CMSOdefinable property.

The family of judicious partitioning problems, introduced by Bollob\'as and
Scott to the field of extremal combinatorics, has been extensively studied from
a structural point of view for over two decades. This rich realm of problems
aims to counterbalance the objectives of classical partitioning problems such
as Min Cut, Min Bisection and Max Cut. While these classical problems focus
solely on the minimization/maximization of the number of edges crossing the
cut, judicious (bi)partitioning problems ask the natural question of the
minimization/maximization of the number of edges lying in the (two) sides of
the cut. In particular, Judicious Bipartition (JB) seeks a bipartition that is
"judicious" in the sense that neither side is burdened by too many edges, and
Balanced JB also requires that the sizes of the sides themselves are "balanced"
in the sense that neither of them is too large. Both of these problems were
defined in the work by Bollob\'as and Scott, and have received notable
scientific attention since then. In this paper, we shed light on the study of
judicious partitioning problems from the viewpoint of algorithm design.
Specifically, we prove that BJB is FPT (which also proves that JB is FPT).

Seymour's decomposition theorem for regular matroids is a fundamental result
with a number of combinatorial and algorithmic applications. In this work we
demonstrate how this theorem can be used in the design of parameterized
algorithms on regular matroids. We consider the problem of covering a set of
vectors of a given finite dimensional linear space (vector space) by a subspace
generated by a set of vectors of minimum size. Specifically, in the Space Cover
problem, we are given a matrix M and a subset of its columns T; the task is to
find a minimum set F of columns of M disjoint with T such that that the linear
span of F contains all vectors of T. For graphic matroids this problem is
essentially Stainer Forest and for cographic matroids this is a generalization
of Multiway Cut. Our main result is the algorithm with running time
2^{O(k)}M ^{O(1)} solving Space Cover in the case when M is a totally
unimodular matrix over rationals, where k is the size of F. In other words, we
show that on regular matroids the problem is fixedparameter tractable
parameterized by the rank of the covering subspace.

For a family of graphs $\cal F$, the $\mathcal{F}$Contraction problem takes
as an input a graph $G$ and an integer $k$, and the goal is to decide if there
exists $S \subseteq E(G)$ of size at most $k$ such that $G/S$ belongs to $\cal
F$. Here, $G/S$ is the graph obtained from $G$ by contracting all the edges in
$S$. Heggernes et al.~[Algorithmica (2014)] were the first to study edge
contraction problems in the realm of Parameterized Complexity. They studied
$\cal F$Contraction when $\cal F$ is a simple family of graphs such as trees
and paths. In this paper, we study the $\mathcal{F}$Contraction problem, where
$\cal F$ generalizes the family of trees. In particular, we define this
generalization in a "parameterized way". Let $\mathbb{T}_\ell$ be the family of
graphs such that each graph in $\mathbb{T}_\ell$ can be made into a tree by
deleting at most $\ell$ edges. Thus, the problem we study is
$\mathbb{T}_\ell$Contraction. We design an FPT algorithm for
$\mathbb{T}_\ell$Contraction running in time
$\mathcal{O}((2\sqrt(\ell))^{\mathcal{O}(k + \ell)} \cdot n^{\mathcal{O}(1)})$.
Furthermore, we show that the problem does not admit a polynomial kernel when
parameterized by $k$. Inspired by the negative result for the kernelization, we
design a lossy kernel for $\mathbb{T}_\ell$Contraction of size $
\mathcal{O}([k(k + 2\ell)] ^{(\lceil {\frac{\alpha}{\alpha1}\rceil + 1)}})$.

The Balanced Stable Marriage problem is a central optimization version of the
classic Stable Marriage problem. Here, the output cannot be an arbitrary stable
matching, but one that balances between the dissatisfaction of the two parties,
men and women. We study Balanced Stable Marriage from the viewpoint of
Parameterized Complexity. Our "above guarantee parameterizations" are arguably
the most natural parameterizations of the problem at hand. Indeed, our
parameterizations precisely fit the scenario where there exists a stable
marriage that both parties would accept, that is, where the satisfaction of
each party is "close" to the best it can hope for. Furthermore, our
parameterizations accurately draw the line between tractability and
intractability with respect to the target value.

Stable Marriage is a fundamental problem to both computer science and
economics. Four wellknown NPhard optimization versions of this problem are
the SexEqual Stable Marriage (SESM), Balanced Stable Marriage (BSM),
maxStable Marriage with Ties (maxSMT) and minStable Marriage with Ties
(minSMT) problems. In this paper, we analyze these problems from the viewpoint
of Parameterized Complexity. We conduct the first study of these problems with
respect to the parameter treewidth. First, we study the treewidth $\mathtt{tw}$
of the primal graph. We establish that all four problems are W[1]hard. In
particular, while it is easy to show that all four problems admit algorithms
that run in time $n^{O(\mathtt{tw})}$, we prove that all of these algorithms
are likely to be essentially optimal. Next, we study the treewidth
$\mathtt{tw}$ of the rotation digraph. In this context, the maxSMT and minSMT
are not defined. For both SESM and BSM, we design (nontrivial) algorithms that
run in time $2^{\mathtt{tw}}n^{O(1)}$. Then, for both SESM and BSM, we also
prove that unless SETH is false, algorithms that run in time
$(2\epsilon)^{\mathtt{tw}}n^{O(1)}$ do not exist for any fixed $\epsilon>0$.
We thus present a comprehensive, complete picture of the behavior of central
optimization versions of Stable Marriage with respect to treewidth.

For a family of graphs $\cal F$, the canonical Weighted $\cal F$ Vertex
Deletion problem is defined as follows: given an $n$vertex undirected graph
$G$ and a weight function $w: V(G)\rightarrow\mathbb{R}$, find a minimum weight
subset $S\subseteq V(G)$ such that $GS$ belongs to $\cal F$. We devise a
recursive scheme to obtain $O(\log^{O(1)}n)$approximation algorithms for such
problems, building upon the classic technique of finding balanced separators in
a graph. Roughly speaking, our scheme applies to problems where an optimum
solution $S$, together with a wellstructured set $X$, form a balanced
separator of $G$. We obtain the first $O(\log^{O(1)}n)$approximation
algorithms for the following problems.
* We give an $O(\log^2n)$factor approximation algorithm for Weighted Chordal
Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal
graphs. On the way, we also obtain a constant factor approximation algorithm
for Multicut on chordal graphs.
* We give an $O(\log^3n)$factor approximation algorithm for Weighted
Distance Hereditary Vertex Deletion (WDHVD). This is the vertex deletion
problem to the family of distance hereditary graphs, or equivalently, the
family of graphs of rankwidth 1.
Our methods also allow us to obtain in a clean fashion a
$O(\log^{1.5}n)$approximation algorithm for the Weighted $\cal F$ Vertex
Deletion problem when $\cal F$ is a minor closed family excluding at least one
planar graph. For the unweighted version of the problem constant factor
approximation algorithms are were known~[Fomin et al., FOCS~2012], while for
the weighted version considered here an $O(\log n \log\log n)$approximation
algorithm follows from~[Bansal et al., SODA~2017]. We believe that our
recursive scheme can be applied to obtain $O(\log^{O(1)}n)$approximation
algorithms for many other problems as well.

Given a graph $G$ and a parameter $k$, the Chordal Vertex Deletion (CVD)
problem asks whether there exists a subset $U\subseteq V(G)$ of size at most
$k$ that hits all induced cycles of size at least 4. The existence of a
polynomial kernel for CVD was a wellknown open problem in the field of
Parameterized Complexity. Recently, Jansen and Pilipczuk resolved this question
affirmatively by designing a polynomial kernel for CVD of size
$O(k^{161}\log^{58}k)$, and asked whether one can design a kernel of size
$O(k^{10})$. While we do not completely resolve this question, we design a
significantly smaller kernel of size $O(k^{12}\log^{10}k)$, inspired by the
$O(k^2)$size kernel for Feedback Vertex Set. Furthermore, we introduce the
notion of the independence degree of a vertex, which is our main conceptual
contribution.

The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$
contains $k$ vertexdisjoint cycles. Since the publication of the classic
Erd\H{o}sP\'osa theorem in 1965, this problem received significant scientific
attention in the fields of Graph Theory and Algorithm Design. In particular,
this problem is one of the first problems studied in the framework of
Parameterized Complexity. The nonuniform fixedparameter tractability of Cycle
Packing follows from the RobertsonSeymour theorem, a fact already observed by
Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle
Packing can be solved in time $2^{\mathcal{O}(k^2)}\cdot V$ using exponential
space. In case a solution exists, Bodlaender's algorithm also outputs a
solution (in the same time). It has later become common knowledge that Cycle
Packing admits a $2^{\mathcal{O}(k\log^2k)}\cdot V$time (deterministic)
algorithm using exponential space, which is a consequence of the
Erd\H{o}sP\'osa theorem. Nowadays, the design of this algorithm is given as an
exercise in textbooks on Parameterized Complexity. Yet, no algorithm that runs
in time $2^{o(k\log^2k)}\cdot V^{\mathcal{O}(1)}$, beating the bound
$2^{\mathcal{O}(k\log^2k)}\cdot V^{\mathcal{O}(1)}$, has been found. In light
of this, it seems natural to ask whether the $2^{\mathcal{O}(k\log^2k)}\cdot
V^{\mathcal{O}(1)}$ bound is essentially optimal. In this paper, we answer
this question negatively by developing a
$2^{\mathcal{O}(\frac{k\log^2k}{\log\log k})}\cdot V$time (deterministic)
algorithm for Cycle Packing. In case a solution exists, our algorithm also
outputs a solution (in the same time). Moreover, apart from beating the bound
$2^{\mathcal{O}(k\log^2k)}\cdot V^{\mathcal{O}(1)}$, our algorithm runs in
time linear in $V$, and its space complexity is polynomial in the input size.

The question of the existence of a polynomial kernelization of the Vertex
Cover Above LP problem has been a longstanding, notorious open problem in
Parameterized Complexity. Five years ago, the breakthrough work by Kratsch and
Wahlstrom on representative sets has finally answered this question in the
affirmative [FOCS 2012]. In this paper, we present an alternative, algebraic
compression of the Vertex Cover Above LP problem into the Rank Vertex Cover
problem. Here, the input consists of a graph G, a parameter k, and a bijection
between V (G) and the set of columns of a representation of a matriod M, and
the objective is to find a vertex cover whose rank is upper bounded by k.

We present two new combinatorial tools for the design of parameterized
algorithms. The first is a simple linear time randomized algorithm that given
as input a $d$degenerate graph $G$ and an integer $k$, outputs an independent
set $Y$, such that for every independent set $X$ in $G$ of size at most $k$,
the probability that $X$ is a subset of $Y$ is at least $\left({(d+1)k \choose
k} \cdot k(d+1)\right)^{1}$.The second is a new (deterministic) polynomial
time graph sparsification procedure that given a graph $G$, a set $T = \{\{s_1,
t_1\}, \{s_2, t_2\}, \ldots, \{s_\ell, t_\ell\}\}$ of terminal pairs and an
integer $k$, returns an induced subgraph $G^\star$ of $G$ that maintains all
the inclusion minimal multicuts of $G$ of size at most $k$, and does not
contain any $(k+2)$vertex connected set of size $2^{{\cal O}(k)}$. In
particular, $G^\star$ excludes a clique of size $2^{{\cal O}(k)}$ as a
topological minor. Put together, our new tools yield new randomized fixed
parameter tractable (FPT) algorithms for Stable $s$$t$ Separator, Stable Odd
Cycle Transversal and Stable Multicut on general graphs, and for Stable
Directed Feedback Vertex Set on $d$degenerate graphs, resolving two problems
left open by Marx et al. [ACM Transactions on Algorithms, 2013]. All of our
algorithms can be derandomized at the cost of a small overhead in the running
time.

We give algorithms with running time $2^{O({\sqrt{k}\log{k}})} \cdot
n^{O(1)}$ for the following problems. Given an $n$vertex unit disk graph $G$
and an integer $k$, decide whether $G$ contains (1) a path on exactly/at least
$k$ vertices, (2) a cycle on exactly $k$ vertices, (3) a cycle on at least $k$
vertices, (4) a feedback vertex set of size at most $k$, and (5) a set of $k$
pairwise vertexdisjoint cycles. For the first three problems, no
subexponential time parameterized algorithms were previously known. For the
remaining two problems, our algorithms significantly outperform the previously
best known parameterized algorithms that run in time $2^{O(k^{0.75}\log{k})}
\cdot n^{O(1)}$. Our algorithms are based on a new kind of tree decompositions
of unit disk graphs where the separators can have size up to $k^{O(1)}$ and
there exists a solution that crosses every separator at most $O(\sqrt{k})$
times. The running times of our algorithms are optimal up to the $\log{k}$
factor in the exponent, assuming the Exponential Time Hypothesis.

A directed odd cycle transversal of a directed graph (digraph) $D$ is a
vertex set $S$ that intersects every odd directed cycle of $D$. In the Directed
Odd Cycle Transversal (DOCT) problem, the input consists of a digraph $D$ and
an integer $k$. The objective is to determine whether there exists a directed
odd cycle transversal of $D$ of size at most $k$.
In this paper, we settle the parameterized complexity of DOCT when
parameterized by the solution size $k$ by showing that DOCT does not admit an
algorithm with running time $f(k)n^{O(1)}$ unless FPT = W[1]. On the positive
side, we give a factor $2$ fixed parameter tractable (FPT) approximation
algorithm for the problem. More precisely, our algorithm takes as input $D$ and
$k$, runs in time $2^{O(k^2)}n^{O(1)}$, and either concludes that $D$ does not
have a directed odd cycle transversal of size at most $k$, or produces a
solution of size at most $2k$. Finally, we provide evidence that there exists
$\epsilon > 0$ such that DOCT does not admit a factor $(1+\epsilon)$
FPTapproximation algorithm.

A Group Labeled Graph is a pair $(G,\Lambda)$ where $G$ is an oriented graph
and $\Lambda$ is a mapping from the arcs of $G$ to elements of a group. A (not
necessarily directed) cycle $C$ is called nonnull if for any cyclic ordering
of the arcs in $C$, the group element obtained by `adding' the labels on
forward arcs and `subtracting' the labels on reverse arcs is not the identity
element of the group. Nonnull cycles in group labeled graphs generalize
several wellknown graph structures, including odd cycles.
In this paper, we prove that nonnull cycles on Group Labeled Graphs have the
halfintegral Erd\"osP\'osa property. That is, there is a function $f:{\mathbb
N}\to {\mathbb N}$ such that for any $k\in {\mathbb N}$, any group labeled
graph $(G,\Lambda)$ has a set of $k$ nonnull cycles such that each vertex of
$G$ appears in at most two of these cycles or there is a set of at most $f(k)$
vertices that intersects every nonnull cycle. Since it is known that nonnull
cycles do not have the integeral Erd\"osP\'osa property in general, a
halfintegral Erd\"osP\'osa result is the best one could hope for.

In the Survivable Network Design Problem (SNDP), the input is an
edgeweighted (di)graph $G$ and an integer $r_{uv}$ for every pair of vertices
$u,v\in V(G)$. The objective is to construct a subgraph $H$ of minimum weight
which contains $r_{uv}$ edgedisjoint (or nodedisjoint) $u$$v$ paths. This is
a fundamental problem in combinatorial optimization that captures numerous
wellstudied problems in graph theory and graph algorithms. In this paper, we
consider the version of the problem where we are given a $\lambda$edge
connected (di)graph $G$ with a nonnegative weight function $w$ on the edges
and an integer $k$, and the objective is to find a minimum weight spanning
subgraph $H$ that is also $\lambda$edge connected, and has at least $k$ fewer
edges than $G$. In other words, we are asked to compute a maximum weight subset
of edges, of cardinality up to $k$, which may be safely deleted from $G$.
Motivated by this question, we investigate the connectivity properties of
$\lambda$edge connected (di)graphs and obtain algorithmically significant
structural results. We demonstrate the importance of our structural results by
presenting an algorithm running in time $2^{O(k \log k)} V(G)^{O(1)}$ for
$\lambda$ECS, thus proving its fixedparameter tractability. We follow up on
this result and obtain the {\em first polynomial compression} for $\lambda$ECS
on unweighted graphs. As a consequence, we also obtain the first fixed
parameter tractable algorithm, and a polynomial kernel for a parameterized
version of the classic Mininum Equivalent Graph problem. We believe that our
structural results are of independent interest and will play a crucial role in
the design of algorithms for connectivityconstrained problems in general and
the SNDP problem in particular.

In this paper we consider Simultaneous Feedback Edge Set (SimFES) problem.
In this problem, the input is an $n$vertex graph $G$, an integer $k$ and a
coloring function ${\sf col}: E(G) \rightarrow 2^{[\alpha]}$ and the objective
is to check whether there is an edge subset $S$ of cardinality at most $k$ in
$G$ such that for all $i \in [\alpha]$, $G_i  S$ is acyclic. Here, $G_i=(V(G),
\{e\in E(G) \mid i \in {\sf col}(e)\})$ and $[\alpha]=\{1,\ldots,\alpha\}$.
When $\alpha =1$, the problem is polynomial time solvable. We show that for
$\alpha =3$ SimFES is NPhard by giving a reduction from Vertex Cover on cubic
graphs. The same reduction shows that the problem does not admit an algorithm
of running time $O(2^{o(k)}n^{O(1)})$ unless ETH fails. This hardness result is
complimented by an FPT algorithm for SimFES running in time $O(2^{\omega
k\alpha+\alpha \log k} n^{O(1)})$, where $\omega$ is the exponent in the
running time of matrix multiplication. The same algorithm gives a polynomial
time algorithm for the case when $\alpha =2$. We also give a kernel for SimFES
with $(k\alpha)^{O(\alpha)}$ vertices. Finally, we consider the problem Maximum
Simultaneous Acyclic Subgraph. Here, the input is a graph $G$, an integer $q$
and, a coloring function ${\sf col}: E(G) \rightarrow 2^{[\alpha]}$. The
question is whether there is a edge subset $F$ of cardinality at least $q$ in
$G$ such that for all $i\in [\alpha]$, $G[F_i]$ is acyclic. Here, $F_i=\{e \in
F \mid i \in \textsf{col}(e)\}$. We give an FPT algorithm for running in time
$O(2^{\omega q \alpha}n^{O(1)})$.

In this paper we propose a new framework for analyzing the performance of
preprocessing algorithms. Our framework builds on the notion of kernelization
from parameterized complexity. However, as opposed to the original notion of
kernelization, our definitions combine well with approximation algorithms and
heuristics. The key new definition is that of a polynomial size
$\alpha$approximate kernel. Loosely speaking, a polynomial size
$\alpha$approximate kernel is a polynomial time preprocessing algorithm that
takes as input an instance $(I,k)$ to a parameterized problem, and outputs
another instance $(I',k')$ to the same problem, such that $I'+k' \leq
k^{O(1)}$. Additionally, for every $c \geq 1$, a $c$approximate solution $s'$
to the preprocessed instance $(I',k')$ can be turned in polynomial time into a
$(c \cdot \alpha)$approximate solution $s$ to the original instance $(I,k)$.
Our main technical contribution are $\alpha$approximate kernels of
polynomial size for three problems, namely Connected Vertex Cover, Disjoint
Cycle Packing and Disjoint Factors. These problems are known not to admit any
polynomial size kernels unless $NP \subseteq coNP/poly$. Our approximate
kernels simultaneously beat both the lower bounds on the (normal) kernel size,
and the hardness of approximation lower bounds for all three problems. On the
negative side we prove that Longest Path parameterized by the length of the
path and Set Cover parameterized by the universe size do not admit even an
$\alpha$approximate kernel of polynomial size, for any $\alpha \geq 1$, unless
$NP \subseteq coNP/poly$. In order to prove this lower bound we need to combine
in a nontrivial way the techniques used for showing kernelization lower bounds
with the methods for showing hardness of approximation

A vertex subset $S$ in a graph $G$ is a dominating set if every vertex not
contained in $S$ has a neighbor in $S$. A dominating set $S$ is a connected
dominating set if the subgraph $G[S]$ induced by $S$ is connected. A connected
dominating set $S$ is a minimal connected dominating set if no proper subset of
$S$ is also a connected dominating set. We prove that there exists a constant
$\varepsilon > 10^{50}$ such that every graph $G$ on $n$ vertices has at most
$O(2^{(1\varepsilon)n})$ minimal connected dominating sets. For the same
$\varepsilon$ we also give an algorithm with running time
$2^{(1\varepsilon)n}\cdot n^{O(1)}$ to enumerate all minimal connected
dominating sets in an input graph $G$.

In the Directed Feedback Vertex Set (DFVS) problem, the input is a directed
graph $D$ on $n$ vertices and $m$ edges, and an integer $k$. The objective is
to determine whether there exists a set of at most $k$ vertices intersecting
every directed cycle of $D$. Whether or not DFVS admits a fixed parameter
tractable (FPT) algorithm was considered the most important open problem in
parameterized complexity until Chen, Liu, Lu, O'Sullivan and Razgon [JACM 2008]
answered the question in the affirmative. They gave an algorithm for the
problem with running time $O(k!4^kk^4nm)$. Since then, no faster algorithm for
the problem has been found. In this paper, we give an algorithm for DFVS with
running time $O(k!4^kk^5(n+m))$. Our algorithm is the first algorithm for DFVS
with linear dependence on input size. Furthermore, the asymptotic dependence of
the running time of our algorithm on the parameter $k$ matches up to a factor
$k$ the algorithm of Chen, Liu, Lu, O'Sullivan and Razgon.
On the way to designing our algorithm for DFVS, we give a general methodology
to shave off a factor of $n$ from iterativecompression based algorithms for a
few other wellstudied covering problems in parameterized complexity. We
demonstrate the applicability of this technique by speeding up by a factor of
$n$, the current best FPT algorithms for Multicut [STOC 2011, SICOMP 2014] and
Directed Subset Feedback Vertex Set [ICALP 2012, TALG 2014].

We consider the fundamental Matroid Theory problem of finding a circuit in a
matroid spanning a set T of given terminal elements. For graphic matroids this
corresponds to the problem of finding a simple cycle passing through a set of
given terminal edges in a graph. The algorithmic study of the problem on
regular matroids, a superclass of graphic matroids, was initiated by
Gaven\v{c}iak, Kr\'al', and Oum [ICALP'12], who proved that the case of the
problem with T=2 is fixedparameter tractable (FPT) when parameterized by the
length of the circuit. We extend the result of Gaven\v{c}iak, Kr\'al', and Oum
by showing that for regular matroids
 the Minimum Spanning Circuit problem, deciding whether there is a circuit
with at most \ell elements containing T, is FPT parameterized by k=\ellT;
 the Spanning Circuit problem, deciding whether there is a circuit
containing T, is FPT parameterized by T. We note that extending our
algorithmic findings to binary matroids, a superclass of regular matroids, is
highly unlikely: Minimum Spanning Circuit parameterized by \ell is W[1]hard on
binary matroids even when T=1. We also show a limit to how far our results
can be strengthened by considering a smaller parameter. More precisely, we
prove that Minimum Spanning Circuit parameterized by T is W[1]hard even on
cographic matroids, a proper subclass of regular matroids.

The optimization version of the Unique Label Cover problem is at the heart of
the Unique Games Conjecture which has played an important role in the proof of
several tight inapproximability results. In recent years, this problem has been
also studied extensively from the point of view of parameterized complexity.
Cygan et al. [FOCS 2012] proved that this problem is fixedparameter tractable
(FPT) and Wahlstr\"om [SODA 2014] gave an FPT algorithm with an improved
parameter dependence. Subsequently, Iwata, Wahlstr\"om and Yoshida [2014]
proved that the edge version of Unique Label Cover can be solved in linear
FPTtime. That is, there is an FPT algorithm whose dependence on the inputsize
is linear. However, such an algorithm for the node version of the problem was
left as an open problem. In this paper, we resolve this question by presenting
the first lineartime FPT algorithm for Node Unique Label Cover.