
We algorithmize the recent structural characterization for clawfree graphs
by Chudnovsky and Seymour. Building on this result, we show that Dominating Set
on clawfree graphs is (i) fixedparameter tractable and (ii) even possesses a
polynomial kernel. To complement these results, we establish that Dominating
Set is not fixedparameter tractable on the slightly larger class of graphs
that exclude K_{1,4} as an induced subgraph (K_{1,4}free graphs). We show that
our algorithmization can also be used to show that the related Connected
Dominating Set problem is fixedparameter tractable on clawfree graphs. To
complement that result, we show that Connected Dominating Set has no polynomial
kernel on clawfree graphs and is not fixedparameter tractable on K_{1,4}free
graphs. Combined, our results provide a dichotomy for Dominating Set and
Connected Dominating Set on K_{1,L}free graphs and show that the problem is
fixedparameter tractable if and only if L <= 3.

In algorithmic graph theory, a classic open question is to determine the
complexity of the Maximum Independent Set problem on $P_t$free graphs, that
is, on graphs not containing any induced path on $t$ vertices. So far,
polynomialtime algorithms are known only for $t\le 5$ [Lokshtanov et al., SODA
2014, 570581, 2014], and an algorithm for $t=6$ announced recently [Grzesik
et al. Arxiv 1707.05491, 2017]. Here we study the existence of
subexponentialtime algorithms for the problem: we show that for any $t\ge 1$,
there is an algorithm for Maximum Independent Set on $P_t$free graphs whose
running time is subexponential in the number of vertices. Even for the weighted
version MWIS, the problem is solvable in $2^{O(\sqrt {tn \log n})}$ time on
$P_t$free graphs. For approximation of MIS in broomfree graphs, a similar
time bound is proved.
Scattered Set is the generalization of Maximum Independent Set where the
vertices of the solution are required to be at distance at least $d$ from each
other. We give a complete characterization of those graphs $H$ for which
$d$Scattered Set on $H$free graphs can be solved in time subexponential in
the size of the input (that is, in the number of vertices plus the number of
edges): If every component of $H$ is a path, then $d$Scattered Set on $H$free
graphs with $n$ vertices and $m$ edges can be solved in time
$2^{O(V(H)\sqrt{n+m}\log (n+m))}$, even if $d$ is part of the input.
Otherwise, assuming the ExponentialTime Hypothesis (ETH), there is no
$2^{o(n+m)}$time algorithm for $d$Scattered Set for any fixed $d\ge 3$ on
$H$free graphs with $n$vertices and $m$edges.

A disconnected cut of a connected graph is a vertex cut that itself also
induces a disconnected subgraph. The decision problem whether a graph has a
disconnected cut is called Disconnected Cut. This problem is closely related to
several homomorphism and contraction problems, and fits in an extensive line of
research on vertex cuts with additional properties. It is known that
Disconnected Cut is NPhard on general graphs, while polynomialtime algorithms
are known for several graph classes. However, the complexity of the problem on
clawfree graphs remained an open question. Its connection to the complexity of
the problem to contract a clawfree graph to the 4vertex cycle $C_4$ led Ito
et al. (TCS 2011) to explicitly ask to resolve this open question.
We prove that Disconnected Cut is polynomialtime solvable on clawfree
graphs, answering the question of Ito et al. The centerpiece of our result is a
novel decomposition theorem for clawfree graphs of diameter 2, which we
believe is of independent interest and expands the research line initiated by
Chudnovsky and Seymour (JCTB 20072012) and Hermelin et al. (ICALP 2011). On
our way to exploit this decomposition theorem, we characterize how disconnected
cuts interact with certain cobipartite subgraphs, and prove two further novel
algorithmic results, namely Disconnected Cut is polynomialtime solvable on
circulararc graphs and line graphs.

A wellstudied coloring problem is to assign colors to the edges of a graph
$G$ so that, for every pair of vertices, all edges of at least one shortest
path between them receive different colors. The minimum number of colors
necessary in such a coloring is the strong rainbow connection number
($\src(G)$) of the graph. When proving upper bounds on $\src(G)$, it is natural
to prove that a coloring exists where, for \emph{every} shortest path between
every pair of vertices in the graph, all edges of the path receive different
colors. Therefore, we introduce and formally define this more restricted edge
coloring number, which we call \emph{very strong rainbow connection number}
($\vsrc(G)$).
In this paper, we give upper bounds on $\vsrc(G)$ for several graph classes,
some of which are tight. These immediately imply new upper bounds on $\src(G)$
for these classes, showing that the study of $\vsrc(G)$ enables meaningful
progress on bounding $\src(G)$. Then we study the complexity of the problem to
compute $\vsrc(G)$, particularly for graphs of bounded treewidth, and show this
is an interesting problem in its own right. We prove that $\vsrc(G)$ can be
computed in polynomial time on cactus graphs; in contrast, this question is
still open for $\src(G)$. We also observe that deciding whether $\vsrc(G) = k$
is fixedparameter tractable in $k$ and the treewidth of $G$. Finally, on
general graphs, we prove that there is no polynomialtime algorithm to decide
whether $\vsrc(G) \leq 3$ nor to approximate $\vsrc(G)$ within a factor
$n^{1\varepsilon}$, unless P$=$NP.

A graph $G$ is a $(\Pi_A,\Pi_B)$graph if $V(G)$ can be bipartitioned into
$A$ and $B$ such that $G[A]$ satisfies property $\Pi_A$ and $G[B]$ satisfies
property $\Pi_B$. The $(\Pi_{A},\Pi_{B})$Recognition problem is to recognize
whether a given graph is a $(\Pi_A,\Pi_B)$graph. There are many
$(\Pi_{A},\Pi_{B})$Recognition problems, including the recognition problems
for bipartite, split, and unipolar graphs. We present efficient algorithms for
many cases of $(\Pi_A,\Pi_B)$Recognition based on a technique which we dub
inductive recognition. In particular, we give fixedparameter algorithms for
two NPhard $(\Pi_{A},\Pi_{B})$Recognition problems, Monopolar Recognition and
2Subcoloring. We complement our algorithmic results with several hardness
results for $(\Pi_{A},\Pi_{B})$Recognition.

We propose polynomialtime algorithms that sparsify planar and boundedgenus
graphs while preserving optimal or nearoptimal solutions to Steiner problems.
Our main contribution is a polynomialtime algorithm that, given an unweighted
graph $G$ embedded on a surface of genus $g$ and a designated face $f$ bounded
by a simple cycle of length $k$, uncovers a set $F \subseteq E(G)$ of size
polynomial in $g$ and $k$ that contains an optimal Steiner tree for any set of
terminals that is a subset of the vertices of $f$.
We apply this general theorem to prove that: * given an unweighted graph $G$
embedded on a surface of genus $g$ and a terminal set $S \subseteq V(G)$, one
can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal
Steiner tree $T$ for $S$ and that has size polynomial in $g$ and $E(T)$; * an
analogous result holds for an optimal Steiner forest for a set $S$ of terminal
pairs; * given an unweighted planar graph $G$ and a terminal set $S \subseteq
V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains
an optimal (edge) multiway cut $C$ separating $S$ and that has size polynomial
in $C$.
In the language of parameterized complexity, these results imply the first
polynomial kernels for Steiner Tree and Steiner Forest on planar and
boundedgenus graphs (parameterized by the size of the tree and forest,
respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by
the size of the cutset). Additionally, we obtain a weighted variant of our main
contribution.

Consider the Maximum Weight Independent Set problem for rectangles: given a
family of weighted axisparallel rectangles in the plane, find a maximumweight
subset of nonoverlapping rectangles. The problem is notoriously hard both in
the approximation and in the parameterized setting. The best known
polynomialtime approximation algorithms achieve superconstant approximation
ratios [Chalermsook and Chuzhoy, SODA 2009; Chan and HarPeled, Discrete &
Comp. Geometry 2012], even though there is a $(1+\epsilon)$approximation
running in quasipolynomial time [Adamaszek and Wiese, FOCS 2013; Chuzhoy and
Ene, FOCS 2016]. When parameterized by the target size of the solution, the
problem is $\mathsf{W}[1]$hard even in the unweighted setting [Marx, FOCS
2007].
To achieve tractability, we study the following shrinking model: one is
allowed to shrink each input rectangle by a multiplicative factor $1\delta$
for some fixed $\delta>0$, but the performance is still compared against the
optimal solution for the original, nonshrunk instance. We prove that in this
regime, the problem admits an EPTAS with running time $f(\epsilon,\delta)\cdot
n^{\mathcal{O}(1)}$, and an FPT algorithm with running time $f(k,\delta)\cdot
n^{\mathcal{O}(1)}$, in the setting where a maximumweight solution of size at
most $k$ is to be computed. This improves and significantly simplifies a PTAS
given earlier for this problem [Adamaszek et al., APPROX 2015], and provides
the first parameterized results for the shrinking model. Furthermore, we
explore kernelization in the shrinking model, by giving efficient kernelization
procedures for several variants of the problem when the input rectangles are
squares.

The metric dimension of a graph $G$ is the size of a smallest subset $L
\subseteq V(G)$ such that for any $x,y \in V(G)$ with $x\not= y$ there is a $z
\in L$ such that the graph distance between $x$ and $z$ differs from the graph
distance between $y$ and $z$. Even though this notion has been part of the
literature for almost 40 years, prior to our work the computational complexity
of determining the metric dimension of a graph was still very unclear. In this
paper, we show tight complexity boundaries for the Metric Dimension problem. We
achieve this by giving two complementary results. First, we show that the
Metric Dimension problem on planar graphs of maximum degree $6$ is NPcomplete.
Then, we give a polynomialtime algorithm for determining the metric dimension
of outerplanar graphs.

Let $d \geq 1$ be an integer. From a set of $d$dimensional vectors, we
obtain a $d$dot product graph by letting each vector ${\bf a}^u$ correspond to
a vertex $u$ and by adding an edge between two vertices $u$ and $v$ if and only
if their dot product ${\bf a}^{u} \cdot {\bf a}^{v} \geq t$, for some fixed,
positive threshold~$t$. Dot product graphs can be used to model social
networks. Recognizing a $d$dot product graph is known to be \NPhard for all
fixed $d\geq 2$. To understand the position of $d$dot product graphs in the
landscape of graph classes, we consider the case $d=2$, and investigate how
$2$dot product graphs relate to a number of other known graph classes.

In the Independent set problem, the input is a graph $G$, every vertex has a
nonnegative integer weight, and the task is to find a set $S$ of pairwise
nonadjacent vertices, maximizing the total weight of the vertices in $S$. We
give an $n^{O (\log^2 n)}$ time algorithm for this problem on graphs excluding
the path $P_6$ on $6$ vertices as an induced subgraph. Currently, there is no
constant $k$ known for which Independent Set on $P_{k}$free graphs becomes
NPcomplete, and our result implies that if such a $k$ exists, then $k > 6$
unless all problems in NP can be decided in (quasi)polynomial time.
Using the combinatorial tools that we develop for the above algorithm, we
also give a polynomialtime algorithm for Efficient Dominating Set on
$P_6$free graphs. In this problem, the input is a graph $G$, every vertex has
an integer weight, and the objective is to find a set $S$ of maximum weight
such that every vertex in $G$ has exactly one vertex in $S$ in its closed
neighborhood, or to determine that no such set exists. Prior to our work, the
class of $P_6$free graphs was the only class of graphs defined by a single
forbidden induced subgraph on which the computational complexity of Efficient
Dominating Set was unknown.

The Steiner Multicut problem asks, given an undirected graph G, terminals
sets T1,...,Tt $\subseteq$ V(G) of size at most p, and an integer k, whether
there is a set S of at most k edges or nodes s.t. of each set Ti at least one
pair of terminals is in different connected components of G \ S. This problem
generalizes several graph cut problems, in particular the Multicut problem (the
case p = 2), which is fixedparameter tractable for the parameter k [Marx and
Razgon, Bousquet et al., STOC 2011].
We provide a dichotomy of the parameterized complexity of Steiner Multicut.
That is, for any combination of k, t, p, and the treewidth tw(G) as constant,
parameter, or unbounded, and for all versions of the problem (edge deletion and
node deletion with and without deletable terminals), we prove either that the
problem is fixedparameter tractable or that the problem is hard (W[1]hard or
even (para)NPcomplete). We highlight that:
 The edge deletion version of Steiner Multicut is fixedparameter tractable
for the parameter k+t on general graphs (but has no polynomial kernel, even on
trees). We present two proofs: one using the randomized contractions technique
of Chitnis et al, and one relying on new structural lemmas that decompose the
Steiner cut into important separators and minimal st cuts.
 In contrast, both node deletion versions of Steiner Multicut are W[1]hard
for the parameter k+t on general graphs.
 All versions of Steiner Multicut are W[1]hard for the parameter k, even
when p=3 and the graph is a tree plus one node. Hence, the results of Marx and
Razgon, and Bousquet et al. do not generalize to Steiner Multicut.
Since we allow k, t, p, and tw(G) to be any constants, our characterization
includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1), and a
polynomial time versus NPhardness dichotomy (by restricting k,t,p,tw(G) to
constant or unbounded).

A graph is called (claw,diamond)free if it contains neither a claw (a
$K_{1,3}$) nor a diamond (a $K_4$ with an edge removed) as an induced subgraph.
Equivalently, (claw,diamond)free graphs can be characterized as line graphs of
trianglefree graphs, or as linear dominoes, i.e., graphs in which every vertex
is in at most two maximal cliques and every edge is in exactly one maximal
clique.
In this paper we consider the parameterized complexity of the
(claw,diamond)free Edge Deletion problem, where given a graph $G$ and a
parameter $k$, the question is whether one can remove at most $k$ edges from
$G$ to obtain a (claw,diamond)free graph. Our main result is that this problem
admits a polynomial kernel. We complement this finding by proving that, even on
instances with maximum degree $6$, the problem is NPcomplete and cannot be
solved in time $2^{o(k)}\cdot V(G)^{O(1)}$ unless the Exponential Time
Hypothesis fail

Paths P1,...,Pk in a graph G=(V,E) are said to be mutually induced if for any
1 <= i < j <= k, Pi and Pj have neither common vertices nor adjacent vertices
(except perhaps their endvertices). The Induced Disjoint Paths problem is to
test whether a graph G with k pairs of specified vertices (si,ti) contains k
mutually induced paths Pi such that Pi connects si and ti for i=1,...,k. We
show that this problem is fixedparameter tractable for clawfree graphs when
parameterized by k. Several related problems, such as the kinaPath problem,
are proven to be fixedparameter tractable for clawfree graphs as well. We
show that an improvement of these results in certain directions is unlikely,
for example by noting that the Induced Disjoint Paths problem cannot have a
polynomial kernel for line graphs (a type of clawfree graphs), unless NP
\subseteq coNP/poly. Moreover, the problem becomes NPcomplete, even when k=2,
for the more general class of K_1,4free graphs. Finally, we show that the
n^O(k)time algorithm of Fiala et al. for testing whether a clawfree graph
contains some kvertex graph H as a topological induced minor is essentially
optimal by proving that this problem is W[1]hard even if G and H are line
graphs.

The Induced Disjoint Paths problem is to test whether a graph G with k
distinct pairs of vertices (s_i,t_i) contains paths P_1,...,P_k such that P_i
connects s_i and t_i for i=1,...,k, and P_i and P_j have neither common
vertices nor adjacent vertices (except perhaps their ends) for 1<=i < j<=k. We
present a lineartime algorithm for Induced Disjoint Paths on circulararc
graphs. For interval graphs, we exhibit a lineartime algorithm for the
generalization of Induced Disjoint Paths where the pairs (s_i,t_i) are not
necessarily distinct.

The Induced Graph Matching problem asks to find k disjoint induced subgraphs
isomorphic to a given graph H in a given graph G such that there are no edges
between vertices of different subgraphs. This problem generalizes the classical
Independent Set and Induced Matching problems, among several other problems. We
show that Induced Graph Matching is fixedparameter tractable in k on clawfree
graphs when H is a fixed connected graph, and even admits a polynomial kernel
when H is a complete graph. Both results rely on a new, strong, and generic
algorithmic structure theorem for clawfree graphs.
Complementing the above positive results, we prove W[1]hardness of Induced
Graph Matching on graphs excluding K_1,4 as an induced subgraph, for any fixed
complete graph H. In particular, we show that Independent Set is W[1]hard on
K_1,4free graphs.
Finally, we consider the complexity of Induced Graph Matching on a large
subclass of clawfree graphs, namely on proper circulararc graphs. We show
that the problem is either polynomialtime solvable or NPcomplete, depending
on the connectivity of H and the structure of G.

Many combinatorial problems involving weights can be formulated as a
socalled ranged problem. That is, their input consists of a universe $U$, a
(succinctlyrepresented) set family $\mathcal{F} \subseteq 2^{U}$, a weight
function $\omega:U \rightarrow \{1,...,N\}$, and integers $0 \leq l \leq u \leq
\infty$. Then the problem is to decide whether there is an $X \in \mathcal{F}$
such that $l \leq \sum_{e \in X}\omega(e) \leq u$. Wellknown examples of such
problems include Knapsack, Subset Sum, Maximum Matching, and Traveling
Salesman. In this paper, we develop a generic method to transform a ranged
problem into an exact problem (i.e. a ranged problem for which $l=u$). We show
that our method has several intriguing applications in exact exponential
algorithms and parameterized complexity, namely:
 In exact exponential algorithms, we present new insight into whether Subset
Sum and Knapsack have efficient algorithms in both time and space. In
particular, we show that the time and space complexity of Subset Sum and
Knapsack are equivalent up to a small polynomial factor in the input size. We
also give an algorithm that solves sparse instances of Knapsack efficiently in
terms of space and time.  In parameterized complexity, we present the first
kernelization results on weighted variants of several wellknown problems. In
particular, we show that weighted variants of Vertex Cover, Dominating Set,
Traveling Salesman and Knapsack all admit polynomial randomized Turing kernels
when parameterized by $U$.
Curiously, our method relies on a technique more commonly found in
approximation algorithms.

We initiate the study of a new parameterization of graph problems. In a
multiple interval representation of a graph, each vertex is associated to at
least one interval of the real line, with an edge between two vertices if and
only if an interval associated to one vertex has a nonempty intersection with
an interval associated to the other vertex. A graph on n vertices is a kgap
interval graph if it has a multiple interval representation with at most n+k
intervals in total. In order to scale up the nice algorithmic properties of
interval graphs (where k=0), we parameterize graph problems by k, and find FPT
algorithms for several problems, including Feedback Vertex Set, Dominating Set,
Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The
Coloring problem turns out to be W[1]hard and we design an XP algorithm for
the recognition problem.

The Firefighter problem is to place firefighters on the vertices of a graph
to prevent a fire with known starting point from lighting up the entire graph.
In each time step, a firefighter may be permanently placed on an unburned
vertex and the fire spreads to its neighborhood in the graph in so far no
firefighters are protecting those vertices. The goal is to let as few vertices
burn as possible. This problem is known to be NPcomplete, even when restricted
to bipartite graphs or to trees of maximum degree three. Initial study showed
the Firefighter problem to be fixedparameter tractable on trees in various
parameterizations. We complete these results by showing that the problem is in
FPT on general graphs when parameterized by the number of burned vertices, but
has no polynomial kernel on trees, resolving an open problem. Conversely, we
show that the problem is W[1]hard when parameterized by the number of unburned
vertices, even on bipartite graphs. For both parameterizations, we additionally
give refined algorithms on trees, improving on the running times of the known
algorithms.