Call for Nominations for Invited Talks 3rd Highlights of Algorithms conference (HALG 2018)

The call for nominations for invited talks for HALG 2018 is open till 12th of December! See below.

Call for Nominations for Invited Talks.
3rd Highlights of Algorithms conference (HALG 2018)
Amsterdam, June 4-6, 2018
http://2018.highlightsofalgorithms.org/

The HALG 2018 conference seeks high-quality nominations for invited talks that will highlight recent advances in algorithmic research. Similarly to previous years, there are two categories of invited talks:
A. survey (60 minutes): a survey of an algorithmic topic that has seen  exciting developments in last couple of years.
B. paper (30 minutes): a significant algorithmic result appearing in a paper in 2017 or later.

To nominate, please email  halg2018.nominations@gmail.com  the following information:
1. Basic details: speaker name + topic (for survey talk) or paper's title, authors, conference/arxiv + preferable speaker (for paper talk).
2. Brief justification: Focus on the benefits to the audience, e.g., quality of results, importance/relevance of topic, clarity of talk, speaker's presentation skills. Pay attention to potentially non-obvious information, e.g., the topic might seem out of scope, or the material seems inadequate for one talk.

All nominations will be reviewed by the Program Committee (PC) to select speakers that will be invited to the conference.

Nominations deadline: December 12, 2017 (for full consideration).

Please keep in mind that the conference does not provide financial support for the speakers.

Best regards,
Robert Krauthgamer,
HALG 2018 PC chair.
====

How pineapples help finding Steiner trees?

The Bratislava Declaration of Young Researchers is something I was involved in recently. Its preparation was inspired by Slovak Presidency of the EU and it was presented on today's informal Council of Ministers responsible for competitiveness (Research). I hope this will have some follow up, as current trend in funding research in EU is in my opinion (and not only my as this declaration shows) going in the wrong direction.
Recently with Marcin Pilipczuk, Micha? Pilipczuk and Erik Jan van Leeuwen we were able to prove that the Steiner Tree problem has a polynomial kernel on unweighted planar graphs. So far this was one of few problems where such kernel seemed possible, but existing tools (e.g. theory of bidimensionality) were unable to deliver it. Essentially, we were able to prove the following theorem.

Theorem 1. Let be a planar Steiner tree instance, and let be the cost of optimum tree connecting terminals in the unweighted graph . One can in polynomial time find a set of edges of size polynomial in that contains an optimal Steiner tree connecting in .

cutopen Figure 1. The process of cutting open the graph along the tree .

Let us shortly discuss the idea of the proof of this theorem. The most non-trivial part of it is the pineapple decomposition. In order to give you a glimpse on this decomposition we will first reduce the problem to the simpler case where all terminals lie on one designated face. Such planar graph with one designated face will be called a brick and this designated face will be called the perimeter of the brick. Without loss of generality we assume that the perimeter is the outer (infinite) face of the plane drawing of the brick. The first step of our reduction is to find 2-approxiate Steiner tree in . Next, we cut the plane open along tree (see Figure 1) to obtain the graph . Now all terminals lie on one face in whereas the optimal Steiner tree in is cut into smaller trees in each spanning some subset of terminals. As we do not know how exactly the optimal tree will be cut, we will prove that a single polynomial kernel exists for all possible subsets of terminals on the perimeter, i.e., the kernel will contain some optimal Steiner tree for every  possible subset of terminals on the perimeter. This is stated in the following theorem.

Theorem 2. Let be a brick. Then one can find in polynomial time a subgraph of such that

  • ,
  • is polynomial in ,
  • for every set , contains some optimal Steiner tree in that connects .

The idea behind the proof of Theorem 2 is to apply it recursively on subbricks (subgraphs enclosed by a simple cycle) of the given brick . The main challenge is to devise an appropriate way to decompose into subbricks, so that their ``measure' decreases. Here we use the perimeter of a brick as a potential that measures the progress of the algorithm.

partitionFigure 2. An optimal Steiner tree and how it partitions the brick into smaller bricks .

Intuitively, we would want to do the following. Let be a tree in that connects a subset of the vertices on the perimeter of . Then splits into a number of smaller bricks , formed by the finite faces of (see Figure 2). We recurse on bricks , obtaining graphs , and return . We can prove that this decomposition yields a polynomial bound on if (i) all bricks have multiplicatively smaller perimeter than , and (ii) the sum of the perimeters of the subbricks is linear in the perimeter of .

In this approach, there are two clear issues that need to be solved. The first issue is that we need an algorithm to decide whether there is a tree for which the induced set of subbricks satisfies conditions (i) and (ii). We design a dynamic programming algorithm that either correctly decides that no such tree exists, or finds a set of subbricks of that satisfies condition (i) and (ii). In the latter case, we can recurse on each of those subbricks.

doubleFigure 3. An optimal Steiner tree that connects a set of vertices on the perimeter of and that consists of two small trees that are connected by a long path ; note that both bricks neighbouring may have perimeter very close to .

The second issue is that there might be no trees for which the induced set of subbricks satisfies conditions (i) and (ii). In this case, optimal Steiner trees, which are a natural candidate for such partitioning trees , behave in a specific way. For example, consider the tree of Figure 3, which consists of two small trees , that lie on opposite sides of the brick and that are connected through a shortest path (of length slightly less than ). Then both faces of that neighbour may have perimeter almost equal to , thus blocking our default decomposition approach.

pineapple2
Figure 4. A cycle that (in particular) hides the small trees in the ring between and , and a subsequent decomposition of into smaller bricks.

To address this second issue, we propose a completely different decomposition - the pineapple decomposition. Intuitively, we find a cycle of length linear in that lies close to , such that all vertices of degree three or more of any optimal Steiner tree are hidden in the ring between and (see Figure 4). We then decompose the ring between and into a number of smaller bricks. We recursively apply Theorem 2 to these bricks, and return the result of these recursive calls together with a set of shortest paths inside between any pair of vertices on . The main technical difficulty is to prove that such circle exists. If you would like to learn more on how it works, you can still attend our talk during the coming FOCS in Philadelphia on Sunday at 11:05, or have look into the full version of the paper on arXiv. Additionally to the above result, the paper contains similar results for planar Steiner forest problem, planar edge multiway cut, as well as some generalization of these results to weighted graphs.

Workshop on Kernelization 2013

Last week we organized Workshop on Kernelization (WorKer 2013) in Warsaw. The programmee included

  • an update meeting on graph cut problems,
  • two tutorials (Matroid theory and kernelization by Saket Saurabh, Stefan Kratsch and Magnus Wahlström and Kernel-size lower bounds: the evidence from complexity theory by Andrew Drucker),
  • two invited talks on techniques used outside the kernelization area which might turn out useful in kernelization (on planar graphs by Piotr Sankowski and on spanners by Seth Pettie)
  • a few short contributed talks

We hope it was fun! Below you can see some pictures.