BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Eurandom - ECPv5.1.4//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Eurandom
X-ORIGINAL-URL:https://www.eurandom.tue.nl
X-WR-CALDESC:Events for Eurandom
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20180101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;VALUE=DATE:20180910
DTEND;VALUE=DATE:20180915
DTSTAMP:20200803T235346
CREATED:20180618T131100Z
LAST-MODIFIED:20180816T113643Z
UID:2045-1536537600-1536969599@www.eurandom.tue.nl
SUMMARY:NWO-JSPS joint seminar: Computations on Networks with a Tree-Structure: From Theory to Practice
DESCRIPTION:Sponsored by\n \nSummary\nDynamic programming based on tree decomposition is one of the most successful approaches for solving important hard problems on networks\, with problems ranging from several application areas (including operations research\, computational biology\, etc.). In theory\, Bodlaender's algorithm and Courcelle's theorem give for a large collection of problems algorithms that solve them in time linear in the number of vertices\, assuming we have a graph or network with the appropriate structure (i.e.\, the treewidth is bounded); a condition that appears to be true for many networks from quite various applications. However\, while these results and the corresponding algorithms play a central role in many theoretical / foundational studies\, and are seen as cornerstones in the field of parameterized algorithms ("fixed parameter tractability")\, the direct practical use is under debate: while asymptotic optimal\, the constant factors hidden in the big-Oh notation are huge. Thus\, a worthy topic of study is to see how the theoretical results can be moved to useful practical results. This asks for the development of new algorithmic insights and algorithm engineering studies\, alongside with further insights in the structure of networks that allow these type of dynamic programming algorithms. This seminar brings together experts from Japan and the Netherlands to initiate new studies towards significant progress both in practice as in theory. In particular\, the seminar focuses on the following research questions: \n\nParallel computations and positive instance driven computation of treewidth\nPractical FPT algorithms for computing treewidth and lower bounds\nComputation of centrality measures of networks\n\n \nOrganizers\n\n\n\nHans Bodlaender\nUniversity of Utrecht / TU Eindhoven\n\n\nBart Jansen\nTU Eindhoven\n\n\nErik Jan van Leeuwen\nUniversity of Utrecht\n\n\nJesper Nederhof\nTU Eindhoven\n\n\nYota Otachi\nKumamoto University\n\n\nTom van der Zanden\nUniversity of Utrecht\n\n\n\n\n\n\n\n \nProgramme\nLink to Time Schedule \n \nAbstracts\nRemy Belmonte (University of Electro-Communications\, Japan) \nParameterized (Approximate) Defective Coloring\nIn Defective Coloring we are given a graph G=(V\,E) and two integers chi_d\,Delta^* and are asked if we can partition V into chi_d color classes\, so that each class induces a graph of maximum degree Delta^*. We investigate the complexity of this generalization of Coloring with respect to several well-studied graph parameters\, and show that the problem is W-hard parameterized by treewidth\, pathwidth\, tree-depth\, or feedback vertex set\, if chi_d=2. As expected\, this hardness can be extended to larger values of chi_d for most of these parameters\, with one surprising exception: we show that the problem is FPT parameterized by feedback vertex set for any chi_d != 2\, and hence 2-coloring is the only hard case for this parameter. In addition to the above\, we give an ETH-based lower bound for treewidth and pathwidth\, showing that no algorithm can solve the problem in n^{o(pw)}\, essentially matching the complexity of an algorithm obtained with standard techniques. We complement these results by considering the problem's approximability and show that\, with respect to Delta^*\, the problem admits an algorithm which for any epsilon>0 runs in time (tw/epsilon)^{O(tw)} and returns a solution with exactly the desired number of colors that approximates the optimal Delta^* within (1+epsilon). We also give a (tw)^{O(tw)} algorithm which achieves the desired Delta^* exactly while 2-approximating the minimum value of chi_d. We show that this is close to optimal\, by establishing that no FPT algorithm can (under standard assumptions) achieve a better than 3/2-approximation to chi_d\, even when an extra constant additive error is also allowed.\n(joint work with Michael Lampis and Valia Mitsou) \n \nHans Bodlaender (Utrecht & Eindhoven\, Netherlands) \nTreewidth and reduction algorithms\nGraph reduction is a useful technique to obtain fast algorithms for recognizing graphs of bounded treewidth\, and solving problems on graphs of bounded treewidth. In this talk\, a number of results are surveyed\, including techniques to compute treewidth through reduction\, and deriving reduction rules for finite index properties and applications to kernelization. The talk ends with a recent application: given a knot diagram of treewidth two\, we can test in linear time whether it represents the unknot. \n \nHuib Donkers (TU Eindhoven) \n F-minor-free deletion parameterised by a treewidth modulator only admits a polynomial Turing kernel for restricted F\nFor a fixed family of graphs F\, the F-minor-free deletion problem takes as input a graph G and integer k and the objective is to determine whether there exists a set S ⊆ V(G) of size at most k such that G-S does not contain any graph of F as a minor. Many classical graph theoretic problems can be expressed as an F-minor-free deletion problem by carefully choosing F. For example when F contains a single K₃ graph\, F-minor-free deletion is equivalent to the Feedback Vertex Set problem.\nFor a parameterised problem with parameter l\, a Turing kernel is a polynomial time algorithm that can solve the problem when given access to an oracle that can solve small instances of the original problem. If the size of these queries can be bounded by a polynomial of l then we say this is a polynomial Turing kernel.\nWe consider the F-minor-free deletion problem parameterised by deletion distance to treewidth t\, where t is the minimum treewidth of all graphs in F. And we show that F-minor-free deletion admits a polynomial Turing kernel if F contains a P₃-subgraph-free graph\, but not for any other F unless certain complexity-theoretic assumptions fail. The same can be said for F-subgraph-free deletion where the objective is to find a vertex set S of size at most k such that G-S does not contain any graph of F as subgraph. \n \nAlex Grigoriev (Maastricht University) \nA survey on possible and impossible attempts to solve the treewidth problem via ILPs\nWe survey a number of integer programming formulations for the pathwidth and for the treewidth problems. The attempts to find good formulations for the problems span the period of 15 years\, yet without any true success. Nevertheless\, some formulations provide potentially useful frameworks for attacking these notorious problems. Some others are just curious and interesting fruits of mathematical imagination. \n \nYoichi Iwata (National Institute of Informatics\, Japan) \nOn the Power of Tree-Depth for Fully Polynomial FPT Algorithms\nThere are many classical problems in P whose time complexities have not been improved over the past decades.\nRecent studies of "Hardness in P" have revealed that\, for several of such problems\, the current fastest algorithm is the best possible under some complexity assumptions. To bypass this difficulty\, the concept of "FPT inside P" has been introduced. For a problem with the current best time complexity O(n^c)\, the goal is to design an algorithm running in k^{O(1)}n^{c'} time for a parameter k and a constant c'