
Sidorenko's Conjecture asserts that every bipartite graph H has the Sidorenko
property, i.e., a quasirandom graph minimizes the density of H among all graphs
with the same edge density. We study a stronger property, which requires that a
quasirandom multipartite graph minimizes the density of H among all graphs with
the same edge densities between its parts; this property is called the step
Sidorenko property. We show that many bipartite graphs fail to have the step
Sidorenko property and use our results to show the existence of a bipartite
edgetransitive graph that is not weakly norming; this answers a question of
Hatami [Israel J. Math. 175 (2010), 125150].

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 $2^{o(t\log t)}\cdot
n^{\mathcal{O}(1)}$ on general directed graphs, where $t$ is the treewidth of
the underlying undirected graph. This is matched by a dynamic programming
algorithm with running time $2^{\mathcal{O}(t\log t)}\cdot n^{\mathcal{O}(1)}$.
On the other hand, we show that if the input digraph is planar, then the
running time can be improved to $2^{\mathcal{O}(t)}\cdot n^{\mathcal{O}(1)}$.

The notion of Turing kernelization investigates whether a polynomialtime
algorithm can solve an NPhard problem, when it is aided by an oracle that can
be queried for the answers to boundedsize subproblems. One of the main open
problems in this direction is whether kPath admits a polynomial Turing kernel:
can a polynomialtime algorithm determine whether an undirected graph has a
simple path of length k, using an oracle that answers queries of size poly(k)?
We show this can be done when the input graph avoids a fixed graph H as a
topological minor, thereby significantly generalizing an earlier result for
boundeddegree and $K_{3,t}$minorfree graphs. Moreover, we show that kPath
even admits a polynomial Turing kernel when the input graph is not
Htopologicalminorfree itself, but contains a known vertex modulator of size
bounded polynomially in the parameter, whose deletion makes it so. To obtain
our results, we build on the graph minors decomposition to show that any
Htopologicalminorfree graph that does not contain a kpath, has a separation
that can safely be reduced after communication with the oracle.

In the Edge Bipartization problem one is given an undirected graph $G$ and an
integer $k$, and the question is whether $k$ edges can be deleted from $G$ so
that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci.,
72(8):13861396, 2006] proposed an algorithm solving this problem in time
$O(2^k m^2)$; today, this algorithm is a textbook example of an application of
the iterative compression technique. Despite extensive progress in the
understanding of the parameterized complexity of graph separation problems in
the recent years, no significant improvement upon this result has been yet
reported.
We present an algorithm for Edge Bipartization that works in time $O(1.977^k
nm)$, which is the first algorithm with the running time dependence on the
parameter better than $2^k$. To this end, we combine the general iterative
compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):13861396,
2006], the technique proposed by Wahlstrom [SODA 2014, 17621781] of using a
polynomialtime solvable relaxation in the form of a Valued Constraint
Satisfaction Problem to guide a boundeddepth branching algorithm, and an
involved Measure & Conquer analysis of the recursion tree.

We consider the following problem for a fixed graph H: given a graph G and
two Hcolorings of G, i.e. homomorphisms from G to H, can one be transformed
(reconfigured) into the other by changing one color at a time, maintaining an
Hcoloring throughout. This is the same as finding a path in the Hom(G,H)
complex. For H=K_k this is the problem of finding paths between kcolorings,
which was shown to be in P for k<=3 and PSPACEcomplete otherwise by Cereceda
et al. 2011. We generalize the positive side of this dichotomy by providing an
algorithm that solves the problem in polynomial time for any H with no C_4
subgraph. This gives a large class of constraints for which finding solutions
to the Constraint Satisfaction Problem is NPcomplete, but finding paths in the
solution space is P.
The algorithm uses a characterization of possible reconfiguration sequences
(paths in Hom(G,H)), whose main part is a purely topological condition
described in algebraic terms of the fundamental groupoid of H seen as a
topological space.

In the multicoloring problem, also known as ($a$:$b$)coloring or $b$fold
coloring, we are given a graph G and a set of $a$ colors, and the task is to
assign a subset of $b$ colors to each vertex of G so that adjacent vertices
receive disjoint color subsets. This natural generalization of the classic
coloring problem (the $b=1$ case) is equivalent to finding a homomorphism to
the Kneser graph $KG_{a,b}$, and gives relaxations approaching the fractional
chromatic number.
We study the complexity of determining whether a graph has an
($a$:$b$)coloring. Our main result is that this problem does not admit an
algorithm with running time $f(b)\cdot 2^{o(\log b)\cdot n}$, for any
computable $f(b)$, unless the Exponential Time Hypothesis (ETH) fails. A
$(b+1)^n\cdot \text{poly}(n)$time algorithm due to Nederlof [2008] shows that
this is tight. A direct corollary of our result is that the graph homomorphism
problem does not admit a $2^{O(n+h)}$ algorithm unless ETH fails, even if the
target graph is required to be a Kneser graph. This refines the understanding
given by the recent lower bound of Cygan et al. [SODA 2016].
The crucial ingredient in our hardness reduction is the usage of detecting
matrices of Lindstr\"om [Canad. Math. Bull., 1965], which is a combinatorial
tool that, to the best of our knowledge, has not yet been used for proving
complexity lower bounds. As a side result, we prove that the running time of
the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for
the rmonomial detection problem are optimal under ETH.

Cutwidth is one of the classic layout parameters for graphs. It measures how
well one can order the vertices of a graph in a linear manner, so that the
maximum number of edges between any prefix and its complement suffix is
minimized. As graphs of cutwidth at most $k$ are closed under taking
immersions, the results of Robertson and Seymour imply that there is a finite
list of minimal immersion obstructions for admitting a cut layout of width at
most $k$. We prove that every minimal immersion obstruction for cutwidth at
most $k$ has size at most $2^{O(k^3\log k)}$.
As an interesting algorithmic byproduct, we design a new fixedparameter
algorithm for computing the cutwidth of a graph that runs in time $2^{O(k^2\log
k)}\cdot n$, where $k$ is the optimum width and $n$ is the number of vertices.
While being slower by a $\log k$factor in the exponent than the fastest known
algorithm, given by Thilikos, Bodlaender, and Serna in [Cutwidth I: A linear
time fixed parameter algorithm, J. Algorithms, 56(1):124, 2005] and [Cutwidth
II: Algorithms for partial $w$trees of bounded degree, J. Algorithms,
56(1):2549, 2005], our algorithm has the advantage of being simpler and
selfcontained; arguably, it explains better the combinatorics of optimumwidth
layouts.

Suppose $\mathcal{F}$ is a finite family of graphs. We consider the following
metaproblem, called $\mathcal{F}$Immersion Deletion: given a graph $G$ and
integer $k$, decide whether the deletion of at most $k$ edges of $G$ can result
in a graph that does not contain any graph from $\mathcal{F}$ as an immersion.
This problem is a close relative of the $\mathcal{F}$Minor Deletion problem
studied by Fomin et al. [FOCS 2012], where one deletes vertices in order to
remove all minor models of graphs from $\mathcal{F}$.
We prove that whenever all graphs from $\mathcal{F}$ are connected and at
least one graph of $\mathcal{F}$ is planar and subcubic, then the
$\mathcal{F}$Immersion Deletion problem admits: a constantfactor
approximation algorithm running in time $O(m^3 \cdot n^3 \cdot \log m)$; a
linear kernel that can be computed in time $O(m^4 \cdot n^3 \cdot \log m)$; and
a $O(2^{O(k)} + m^4 \cdot n^3 \cdot \log m)$time fixedparameter algorithm,
where $n,m$ count the vertices and edges of the input graph.
These results mirror the findings of Fomin et al. [FOCS 2012], who obtained a
similar set of algorithmic results for $\mathcal{F}$Minor Deletion, under the
assumption that at least one graph from $\mathcal{F}$ is planar. An important
difference is that we are able to obtain a linear kernel for
$\mathcal{F}$Immersion Deletion, while the exponent of the kernel of Fomin et
al. for $\mathcal{F}$Minor Deletion depends heavily on the family
$\mathcal{F}$. In fact, this dependence is unavoidable under plausible
complexity assumptions, as proven by Giannopoulou et al. [ICALP 2015]. This
reveals that the kernelization complexity of $\mathcal{F}$Immersion Deletion
is quite different than that of $\mathcal{F}$Minor Deletion.

A graph K is squarefree if it contains no fourcycle as a subgraph. A graph
K is multiplicative if GxH > K implies G > K or H > K, for all graphs G,H.
Here GxH is the tensor (or categorical) graph product and G > K denotes the
existence of a graph homomorphism from G to K. Hedetniemi's conjecture states
that all cliques K_n are multiplicative. However, the only nontrivial graphs
known to be multiplicative are K_3, odd cycles, and still more generally,
circular cliques $K_{p/q}$ with 2 <= p/q < 4. We make no progress for cliques,
but show that all squarefree graphs are multiplicative. In particular, this
gives the first multiplicative graphs of chromatic number higher than 4.
Generalizing, in terms of the box complex, the topological insight behind
existing proofs for odd cycles, we also give a different proof for circular
cliques.

Dynamic programming on path and tree decompositions of graphs is a technique
that is ubiquitous in the field of parameterized and exponentialtime
algorithms. However, one of its drawbacks is that the space usage is
exponential in the decomposition's width. Following the work of Allender et al.
[Theory of Computing, '14], we investigate whether this space complexity
explosion is unavoidable. Using the idea of reparameterization of Cai and
Juedes [J. Comput. Syst. Sci., '03], we prove that the question is closely
related to a conjecture that the Longest Common Subsequence problem
parameterized by the number of input strings does not admit an algorithm that
simultaneously uses XP time and FPT space. Moreover, we complete the complexity
landscape sketched for pathwidth and treewidth by Allender et al. by
considering the parameter treedepth. We prove that computations on treedepth
decompositions correspond to a model of nondeterministic machines that work in
polynomial time and logarithmic space, with access to an auxiliary stack of
maximum height equal to the decomposition's depth. Together with the results of
Allender et al., this describes a hierarchy of complexity classes for
polynomialtime nondeterministic machines with different restrictions on the
access to working space, which mirrors the classic relations between treewidth,
pathwidth, and treedepth.

We investigate the complexity of several fundamental polynomialtime solvable
problems on graphs and on matrices, when the given instance has low treewidth;
in the case of matrices, we consider the treewidth of the graph formed by
nonzero entries. In each of the considered cases, the best known algorithms
working on general graphs run in polynomial time, however the exponent of the
polynomial is large. Therefore, our main goal is to construct algorithms with
running time of the form $\textrm{poly}(k)\cdot n$ or $\textrm{poly}(k)\cdot
n\log n$, where $k$ is the width of the tree decomposition given on the input.
Such procedures would outperform the best known algorithms for the considered
problems already for moderate values of the treewidth, like $O(n^{1/c})$ for
some small constant $c$.
Our results include:
 an algorithm for computing the determinant and the rank of an $n\times n$
matrix using $O(k^3\cdot n)$ time and arithmetic operations;
 an algorithm for solving a system of linear equations using $O(k^3\cdot
n)$ time and arithmetic operations;
 an $O(k^3\cdot n\log n)$time randomized algorithm for finding the
cardinality of a maximum matching in a graph;
 an $O(k^4\cdot n\log^2 n)$time randomized algorithm for constructing a
maximum matching in a graph;
 an $O(k^2\cdot n\log n)$time algorithm for finding a maximum vertex flow
in a directed graph.
Moreover, we give an approximation algorithm for treewidth with time
complexity suited to the running times as above. Namely, the algorithm, when
given a graph $G$ and integer $k$, runs in time $O(k^7\cdot n\log n)$ and
either correctly reports that the treewidth of $G$ is larger than $k$, or
constructs a tree decomposition of $G$ of width $O(k^2)$.

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

A vertexsubset graph problem $Q$ defines which subsets of the vertices of an
input graph are feasible solutions. The reconfiguration version of a
vertexsubset problem $Q$ asks whether it is possible to transform one feasible
solution for $Q$ into another in at most $\ell$ steps, where each step is a
vertex addition or deletion, and each intermediate set is also a feasible
solution for $Q$ of size bounded by $k$. Motivated by recent results
establishing W[1]hardness of the reconfiguration versions of most
vertexsubset problems parameterized by $\ell$, we investigate the complexity
of such problems restricted to graphs of bounded treewidth. We show that the
reconfiguration versions of most vertexsubset problems remain PSPACEcomplete
on graphs of treewidth at most $t$ but are fixedparameter tractable
parameterized by $\ell + t$ for all vertexsubset problems definable in monadic
secondorder logic (MSOL). To prove the latter result, we introduce a technique
which allows us to circumvent cardinality constraints and define
reconfiguration problems in MSOL.

We show that several reconfiguration problems known to be PSPACEcomplete
remain so even when limited to graphs of bounded bandwidth. The essential step
is noticing the similarity to very limited string rewriting systems, whose
ability to directly simulate Turing Machines is classically known. This
resolves a question posed open in [Bonsma P., 2012]. On the other hand, we show
that a large class of reconfiguration problems becomes tractable on graphs of
bounded treedepth, and that this result is in some sense tight.

We present a polynomialtime algorithm that, given two independent sets in a
clawfree graph $G$, decides whether one can be transformed into the other by a
sequence of elementary steps. Each elementary step is to remove a vertex $v$
from the current independent set $S$ and to add a new vertex $w$ (not in $S$)
such that the result is again an independent set. We also consider the more
restricted model where $v$ and $w$ have to be adjacent.