{"id":689,"date":"2014-10-16T12:51:22","date_gmt":"2014-10-16T12:51:22","guid":{"rendered":"http:\/\/corner.mimuw.edu.pl\/?p=689"},"modified":"2022-09-12T09:43:18","modified_gmt":"2022-09-12T09:43:18","slug":"how-pineapples-help-finding-steiner-trees","status":"publish","type":"post","link":"https:\/\/corner.mimuw.edu.pl\/?p=689","title":{"rendered":"How pineapples help finding Steiner trees?"},"content":{"rendered":"<p>The <a href=\"http:\/\/www.eu2016.sk\/data\/documents\/bratislava-declaration-of-young-researchers-final.pdf\">Bratislava Declaration of Young Researchers <\/a>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.<br \/>\nRecently 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.<\/p>\n<p><strong>Theorem 1.<\/strong> <em>Let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_de9a49be5622d307b962e3a828080c71.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be a planar Steiner tree instance, and let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_62474381adb0eaad3155beff459f7124.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be the cost of optimum tree connecting terminals <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the unweighted graph <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. One can in polynomial time find a set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6268ac8f871f6f4457098e1acc648af8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of edges of size polynomial in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_62474381adb0eaad3155beff459f7124.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that contains an optimal Steiner tree connecting <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/em><\/p>\n<p><a href=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/cutopen.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-722 \" src=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/cutopen.png\" alt=\"cutopen\" width=\"625\" height=\"199\" \/><\/a> <strong>Figure 1.<\/strong> The process of cutting open the graph <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> along the tree <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0553a0729312e996d867352daa042435.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>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 <em>brick<\/em> and this designated face will be called the <em>perimeter of the brick<\/em>. 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0553a0729312e996d867352daa042435.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Next, we cut the plane open along tree <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0553a0729312e996d867352daa042435.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (see Figure 1) to obtain the graph <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8fa0f1e919c305d048de19f183c150e0.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Now all terminals lie on one face in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8fa0f1e919c305d048de19f183c150e0.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> whereas the optimal Steiner tree in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_dfcf28d0734569a6a693bc8194de62bf.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is cut into smaller trees in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8fa0f1e919c305d048de19f183c150e0.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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\u00a0 possible subset of terminals on the perimeter. This is stated in the following theorem.<\/p>\n<p><strong>Theorem 2.<\/strong> <em>Let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be a brick. Then one can find in polynomial time a subgraph <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_c1d9f50f86825a1a2302ec2449c17196.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> such that<\/em><\/p>\n<ul>\n<li><em><span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_a3e7def38fdf395c4f153b5b185e321d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>,<\/em><\/li>\n<li><em><span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_4b7a50c43b81758c7d5ab2cfb70a762a.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is polynomial in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_898ba1fc4c98ca520310d46ab704b933.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>,<\/em><\/li>\n<li><em>for every set <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_1f489da2f3e0bb3f5cc224ef7c52adff.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_c1d9f50f86825a1a2302ec2449c17196.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> contains some optimal Steiner tree in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that connects <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/em><\/li>\n<\/ul>\n<p>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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. The main challenge is to devise an appropriate way to decompose <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> into subbricks, so that their ``measure' decreases. Here we use the <em>perimeter<\/em> of a brick as a potential that measures the progress of the algorithm.<\/p>\n<p><a href=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/partition.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-707\" src=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/partition.png\" alt=\"partition\" width=\"200\" height=\"200\" srcset=\"https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/partition.png 348w, https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/partition-150x150.png 150w, https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/partition-300x300.png 300w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/a><strong>Figure 2.<\/strong> An optimal Steiner tree <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and how it partitions the brick <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> into smaller bricks <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b8c0a0cdc935685bd43e4fe8c8203e61.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>Intuitively, we would want to do the following. Let <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> be a tree in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that connects a subset of the vertices on the perimeter of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. Then <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> splits <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> into a number of smaller bricks <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b8c0a0cdc935685bd43e4fe8c8203e61.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, formed by the finite faces of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_86fe88db83d694f543ad51a93b1d9f9f.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (see Figure 2). We recurse on bricks <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_889416bc9630b10072fd7cc713ea8c0a.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, obtaining graphs <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7774855247034d244db878dde390d57c.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and return <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_37886741186622ef9f704ecf114d1012.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. We can prove that this decomposition yields a polynomial bound on <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_744c214c91ecd5f770c4443f4db58df8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> if (i) all bricks <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_889416bc9630b10072fd7cc713ea8c0a.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> have multiplicatively smaller perimeter than <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and (ii) the sum of the perimeters of the subbricks is linear in the perimeter of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that satisfies condition (i) and (ii). In the latter case, we can recurse on each of those subbricks.<\/p>\n<p><a href=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/double.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-706 \" src=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/double.png\" alt=\"double\" width=\"200\" height=\"200\" srcset=\"https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/double.png 349w, https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/double-150x150.png 150w, https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/double-300x300.png 300w\" sizes=\"(max-width: 200px) 100vw, 200px\" \/><\/a><strong>Figure 3.<\/strong> An optimal Steiner tree that connects a set of vertices on the perimeter of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and that consists of two small trees <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0bff1e5fddf042e193e35fafb147738a.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that are connected by a long path <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>; note that both bricks neighbouring <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> may have perimeter very close to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_898ba1fc4c98ca520310d46ab704b933.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>.<\/p>\n<p>The second issue is that there might be no trees <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_b9ece18c950afbfa6b0fdbfa4ff731d3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, behave in a specific way. For example, consider the tree of Figure 3, which consists of two small trees <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2452fee413f58bb9509e88d80d4b9f8d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6a058d102910f33a7d4cf9ea23067b8c.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that lie on opposite sides of the brick <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and that are connected through a shortest path <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (of length slightly less than <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6910627be32016f6032137b412f78c0c.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>). Then both faces of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_86fe88db83d694f543ad51a93b1d9f9f.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that neighbour <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_44c29edb103a2872f519ad0c9a0fdaaa.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> may have perimeter almost equal to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_898ba1fc4c98ca520310d46ab704b933.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, thus blocking our default decomposition approach.<\/p>\n<p><a href=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/pineapple2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-726 size-medium\" src=\"http:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/pineapple2-300x300.png\" alt=\"pineapple2\" width=\"300\" height=\"300\" srcset=\"https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/pineapple2-300x300.png 300w, https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/pineapple2-150x150.png 150w, https:\/\/corner.mimuw.edu.pl\/wp-content\/uploads\/2014\/10\/pineapple2.png 349w\" sizes=\"(max-width: 300px) 100vw, 300px\" \/><\/a><br \/>\n<strong>Figure 4.<\/strong> A cycle <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that (in particular) hides the small trees <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_6f2312e4a0c81ccd1239eed3115ce208.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the ring between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2cd53d08d798105a0c9dec44c31c1934.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and a subsequent decomposition of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_9d5ed678fe57bcca610140957afab571.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> into smaller bricks.<\/p>\n<p>To address this second issue, we propose a completely different decomposition - the pineapple decomposition. Intuitively, we find a cycle <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of length linear in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_898ba1fc4c98ca520310d46ab704b933.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> that lies close to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2cd53d08d798105a0c9dec44c31c1934.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, such that all vertices of degree three or more of any optimal Steiner tree are hidden in the ring between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2cd53d08d798105a0c9dec44c31c1934.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> (see Figure 4). We then decompose the ring between <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2cd53d08d798105a0c9dec44c31c1934.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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 <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> between any pair of vertices on <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. The main technical difficulty is to prove that such circle <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0d61f8370cad1d412f80b84d143e1257.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> 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 <a href=\"http:\/\/arxiv.org\/abs\/1306.6593\">the paper on arXiv<\/a>. 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.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 &hellip; <a href=\"https:\/\/corner.mimuw.edu.pl\/?p=689\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[4,17],"tags":[],"_links":{"self":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/689"}],"collection":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=689"}],"version-history":[{"count":44,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/689\/revisions"}],"predecessor-version":[{"id":1120,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/689\/revisions\/1120"}],"wp:attachment":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=689"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=689"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=689"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}