Opendata, web and dolomites

Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - DISTRUCT (Structure Theory for Directed Graphs)

Teaser

\"One of the early observations in computer science was that manyalgorithmic problems are computationally intractable, formalised by themathematical concept of \"\"NP-hardness\"\". This includes many algorithmicproblems that occur frequently in practice.A particularly rich class of...

Summary

\"One of the early observations in computer science was that many
algorithmic problems are computationally intractable, formalised by the
mathematical concept of \"\"NP-hardness\"\". This includes many algorithmic
problems that occur frequently in practice.

A particularly rich class of these problems can elegantly be
formalised using the concepts of graphs. A graph consists of a set of
objects, called vertices, and a set of edges connecting pairs of
vertices. The set of vertices could be a group of people with edges
representing whether two people know each other or the vertices could
correspond to web pages and the edges correspond to hyperlinks between
webpages.

Graphs can be distinguished between undirected and directed graphs,
depending on whether the edges always go in both directions, such as
in the example of people knowing each other, or can be
directed only in one direction such as in the hyperlink example.

The elegance of graphs as mathematical abstraction is their
simplicity, which allows to abstract from many irrelevant details of
real practical problem instances.

One very successful way to overcome the computational hardness of many
algorithmic problems on graphs, is to study classes of graphs that have
a particularly simple structure, for instance planar graphs that can
be drawn on a sheet of paper without edges crossing each other. It
turned out that this structure can be exploited to design highly
efficient algorithms for hard computational problems on input
instances that are planar graphs. This has led to a very well
developed theory of structural properties of graphs that can be used
in the design of efficient algorithms.

However, much of this work has focussed on undirected graphs. The goal
of this project is to generalise a part of this theory, known as graph
minor theory and nowhere denseness, to the real of directed graphs. In
this way, the objective is to make this structural theory of graphs
applicable also for algorithmic problems that are naturally modelled
as directed graphs.

\"

Work performed

Work so far has concentrated on the first three work packages, WP1 -
WP3.

In WP1 we proposed to work on the directed excluded grid theorem,
directe disjoint paths and the Erdos-Posa property. In this work
package we made very significant progress on all three objectives. For
the Erdos-Posa property we provided a complete characterisation of
those strongly connected digraphs that have the EP property. For
digraphs that are not strongly connected we studied the class of
vertex cyclic digraphs and we have achieved nearly a complete
characterisation for these as well. There are a few open problems left
that we hope to close before submitting it to a journal. The preprint
is available from arXiv.org. (https://arxiv.org/abs/1603.02504)

For routing problems we studied routing under congestion in acyclic
digraphs as a first step. The results were published at MFCS 2016 and
are available at arXiv https://arxiv.org/abs/1605.01866. Furthermore,
we studied the problem whether there is a polynomial time algorithm,
for every fixed k, for solving the k-disjoint paths problems with
congestion 2 on directed graphs. We believe that we have made
significant progress and found a quasi-polynomial time algorithm. We
hope to improve this to polynomial time. A preprint will be available
soon.

As for directed grids, we made very good progress in this aspect as
well. First of all, we significantly improved our directed excluded
grid theorem and provided a much simpler proof. The new proof has been
submitted to the Journal of the AMS and is currently under
review. Directed grids and grid-like structures have been used by
Chekuri and others for routing in directed planar digraphs. For these
applications it would be a great step forward if one could show a
polynomial grid theorem for planar digraphs. We have therefore worked
on this problem and we think we are very close to finish it. I expect
this to be done in the summer 2017. We are also intensively working
on directed tree width sparsification, but the results are not ready
yet.

In WP2 we proposed to work on nowhere crownful and directed bounded
expansion/directed nowhere dense classes. Here we made spectacular
progress. First of all, we studied the corresponding question on the
simpler case of undirected graphs. As a really surprising result we
introduced a new method borrowed from stability theory, a subbranch of
model theory in mathematical logic, to the study of nowhere dense
classes of graphs. This way we managed to improve bounds on the uniformly
quasi-wideness of such classes from many-fold exponential to
polynomial. This has immediate impact on all algorithms using
uniformly quasi-wideness and speeds them up many-fold
exponentially. This is a really surprising result as usually tools from
logic do not yield very efficient bounds. The results were presented
at SODA 2017 and have been invited to the SODA best paper special
issue that will appear at the ACM Transaction on Algorithms.

We also studied kernels for dominating set problems and managed to
pinpoint exactly the classes of undirected graphs having polynomial
kernels for these problems. This one of the first times where
such a precise characterisation can be given.

As a second step we started to use these results for undirected graphs
to develop the corresponding tools in the directed setting, the
objective of WP2. This project has by far exceeded our expectation. We
showed that directed bounded expansion classes can be defined by
generalised colouring numbers, we proved that for such classes we have
very efficient neighbourhood covers, the neighbourhood complexity is
small and we have a splitter game that can be used for bounded depth
search tree methods. The results will be presented at STACS 2017

Since submitting to STACS we have made further progress and we have
now obtained polynomial kernels for dominating set problems on
directed bounded expansion classes and we have been able to prove that
they admit low dag-depth colouring

Final results

The most spectacular results have already been described and put in
context in the work report. Here we briefly highlight the main
achievements:

- using tools form model theory, more precisely stability theory, we
managed to improve the running time of all algorithms using
the uniformly quasi-wideness property of nowhere dense classes of
undirected graphs many times exponentially. This result is
applicable to a broad range of algorithmic problems on nowhere dense
classes and we expect it to have broad impact.

This result far exceeded our expectations when we first started to
look at stable classes of graphs.

- We showed that for classes of digraphs of bounded directed expansion
we nearly have the same set of characterisations and therefore the
same set of algorithmic tools available as for undirected classes of
bounded expansion. This again exceeded by far our expectations when
we started this project as usually translating from the undirected
into the directed world does not come out with such a smooth
theory. We are extremely excited about this project and believe that
this will provide classes with a very elegant algorithm theory.
Also, recent work by Gneis et al have shown that bounded expansion
covers many networks from practical benchmarks so that these results
do become applicable for practical purposes also.

- On directed grids we think we are close to a polynomial grid
theorem for planar digraphs which would have very significant impact
on directed routing problems as studied, e.g. by Chekuri et al.