{"id":539,"date":"2013-10-29T16:09:02","date_gmt":"2013-10-29T16:09:02","guid":{"rendered":"http:\/\/corner.mimuw.edu.pl\/?p=539"},"modified":"2022-09-12T10:04:37","modified_gmt":"2022-09-12T10:04:37","slug":"wg-2014","status":"publish","type":"post","link":"https:\/\/corner.mimuw.edu.pl\/?p=539","title":{"rendered":"WG 2014"},"content":{"rendered":"<p>The <a href=\"http:\/\/www.univ-orleans.fr\/lifo\/evenements\/WG2014\/?rub=cfp\">call for papers for WG 2014 is out<\/a>.<\/p>\n<p>Let me say that I really like the WG series. Not only because WG'08 was my first conference (and now WG'14 the first one I'm in a PC), but mainly because there is always a nice bunch of papers with cute combinatorics, and you always travel back home from WG with a full sack of cool open problems to think on.<\/p>\n<p>Speaking of these, I went through my private \"open problem list\" and found a few problems that, in my opinion, may nicely suit WG. Hey, there are still a few months till the deadline, so why not solve some of the problems and go for a trip to this lovely castle in France?<\/p>\n<p>The problems are from parameterized complexity, since I mostly work in this area. To the best of my knowledge, there are currently open. On all of them I spent some significant time somewhere in the past.<\/p>\n<p>Maybe a small disclaimer is in place: although I found these problems interesting and nice, the techniques to solve them may turn out to be boring, other PC members of WG 2014 may have different opinions on their importance, etc. So, in any sense you should not treat this as some promise that a solution will get into WG. I just wanted to inspire some research, and see solutions to some nice problems I thought about and didn't succeed, and that is the sole motivation for this post \ud83d\ude42<\/p>\n<p><b>Cutting short paths.<\/b> In <a href=\"http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1572528610000678#\">this paper<\/a> the authors study (among others) the following problem: given a (directed or undirected) 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> with source <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_03c7c0ace395d80182db07ae2c30f034.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> and sink <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and integers <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' 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_2db95e8e1a9267b7a1188556b2013b33.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, cut at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> edges of <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> so that a shortest path from <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_03c7c0ace395d80182db07ae2c30f034.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> to <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> is of length larger than <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_2db95e8e1a9267b7a1188556b2013b33.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. They show an FPT algorithm, parameterized by both <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' 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_2db95e8e1a9267b7a1188556b2013b33.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. The question is: does this problem admit a polynomial kernel with respect to this parameterization?<\/p>\n<p><b>Constrained bipartite vertex cover.<\/b> The minimum vertex cover problem in bipartite graphs is solvable in polynomial time. What about the following variant: given a bipartite graph with fixed bipartition <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_31da6f87f19d9cd2264061a0afc2cbb1.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, and integers <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' 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_92eb5ffee6ae2fec3ad71c777531578f.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, find a vertex cover of the graph with at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> vertices in <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7fc56270e7a70fa81a5935b72eacbe29.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_92eb5ffee6ae2fec3ad71c777531578f.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> vertices 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>. This is NP-hard. There is a simple reduction rule: a vertex from <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_7fc56270e7a70fa81a5935b72eacbe29.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of degree larger than <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_92eb5ffee6ae2fec3ad71c777531578f.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> needs to be included in a solution, and symmetrically the same holds for a vertex 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> of degree larger than <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_0cc175b9c0f1b6a831c399e269772661.gif' style='vertical-align: middle; border: none; padding-bottom:2px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>. After this reduction is exhaustively applied, note that a solution may cover at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_842ce4d151e175e643208b3c1ed05d68.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> edges, so we have a kernel of this size. Can you do better with respect to the number of vertices in the kernel? The classical vertex cover problem in arbitrary graphs has a kernel with linear number of vertices.<\/p>\n<p><b>Imbalance minimization.<\/b> Given an undirected 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>, and an ordering <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_57c7f85f916feebbaa4e804352e633df.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> of its vertices, the imbalance of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_1df181eaa1bb40a0067c06ead197170d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in this ordering equals <p style='text-align:center;'><span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_58ef68c547abacfcd75ca8e9f7e5e123.gif' style='vertical-align: middle; border: none;' class='tex' alt=\"\" \/><\/span><script type='math\/tex;  mode=display'><\/script><\/p> that is, the absolute value of the difference between the number of neighbours of <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_1df181eaa1bb40a0067c06ead197170d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> before and after <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_1df181eaa1bb40a0067c06ead197170d.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> in the ordering. The imbalance of the ordering is the sum of the imbalances of all vertices. <a href=\"http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0020019013001774\">Here<\/a> the authors prove that the problem of finding an ordering of imbalance at most <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, parameterized by <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_8ce4b16b22b58894aa86c421e8759df3.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, is FPT. Does this problem admit a polynomial kernel?<\/p>\n<p><b>Max-leaf outbranching, parameterized by treewidth.<\/b> In a directed graph, an outbranching is a subgraph that is a rooted tree, where each arc is directed downwards. In the max-leaf outbranching problem we seek for an outbranching in the given graph with maximum number of leaves. We are interested in solving this problem, when we are given a tree decomposition of <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> of width <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_e358efa489f58062f10dd7316b65649e.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>, that is, we study treewidth DPs. <a href=\"http:\/\/arxiv.org\/abs\/1103.0534\">Here<\/a> we have shown an <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_bc2c39284e98b3742c1175ae778a0db8.gif' style='vertical-align: middle; border: none; ' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script>-time randomized algorithm, but we could not get a matching lower bound (as we did for most other problems studied there). Is <span class='MathJax_Preview'><img src='https:\/\/corner.mimuw.edu.pl\/wp-content\/plugins\/latex\/cache\/tex_1679091c5a880faf6fb5e6087eb1b2dc.gif' style='vertical-align: middle; border: none; padding-bottom:1px;' class='tex' alt=\"\" \/><\/span><script type='math\/tex'><\/script> the optimal base of the exponent? (Of course, assuming Strong ETH). Or maybe you can do better?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The call for papers for WG 2014 is out. Let me say that I really like the WG series. Not only because WG'08 was my first conference (and now WG'14 the first one I'm in a PC), but mainly because &hellip; <a href=\"https:\/\/corner.mimuw.edu.pl\/?p=539\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":5,"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":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/539"}],"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\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=539"}],"version-history":[{"count":14,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/539\/revisions"}],"predecessor-version":[{"id":1128,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=\/wp\/v2\/posts\/539\/revisions\/1128"}],"wp:attachment":[{"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=539"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=539"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/corner.mimuw.edu.pl\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=539"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}