Friday, 25.08.2017
15:00

16:00
Closing the gap between the lower and upper bounds for the computational complexity of the Graph Isomorphism problem still
is a big challenge for mathematicians and computer scientists. While resolving this problem in the general case seems out
of reach, substantial progress has been made for restricted graph classes such as planar graphs. In particular, planar graph
isomorphism has recently been shown to be in L (and thus is Lcomplete) by Datta, Limaye, Nimbhorkar, Thierauf and Wagner.
We generalize the decomposition
technique used in their result to work with minorclosed graph classes whose 3connected members fulfill a fixability condition
and admit a logspace canonization algorithm.
Wednesday, 30.08.2017
11:00

12:00
We introduce graph motif parameters, a class of graph
parameters that depend only on the frequencies of constantsize induced
subgraphs. Classical works by Lovász show that many interesting
quantities have this form, including, for fixed graphs H, the number of
Hcopies (induced or not) in an input graph G, and the number of
homomorphisms from H to G.
Using the framework of graph motif parameters, we obtain faster
algorithms for counting subgraph copies of fixed graphs H in host graphs
G: For graphs H on k edges, we show how to count subgraph copies of H in
time k^{O(k)}⋅n^{0.174k+o(k)} by a surprisingly simple algorithm. This
improves upon previously known running times, such as O(n0.91k+c) time
for kedge matchings or O(n0.46k+c) time for kcycles.
Furthermore, we prove a general complexity dichotomy for evaluating
graph motif parameters: Given a class C of such parameters, we consider
the problem of evaluating f∈C on input graphs G, parameterized by the
number of induced subgraphs that f depends upon. For every recursively
enumerable class C, we prove the above problem to be either FPT or
#W[1]hard, with an explicit dichotomy criterion. This allows us to
recover known dichotomies for counting subgraphs, induced subgraphs, and
homomorphisms in a uniform and simplified way, together with improved
lower bounds.
Finally, we extend graph motif parameters to colored subgraphs and prove
a complexity trichotomy: For vertexcolored graphs H and G, where H is
from a fixed class H, we want to count colorpreserving Hcopies in G.
We show that this problem is either polynomialtime solvable or FPT or
#W[1]hard, and that the FPT cases indeed need FPT time under reasonable
assumptions.
Joint work with Radu Curticapean and Dániel Marx