Program
The workshop program is given below. Slides are available for most of the talks.
Sunday March 3rd, 2019
- 15:00 Check-in
- 19:00 - 21:00 Welcome banquet
Monday March 4th, 2019: Welcome & open problems
- 09:00 - 10:00 Shonan introduction & participant introductions
- 10:00 - 10:30 Coffee break
- 10:30 - 11:00 Continuation of participant introductions
- 11:00 - 12:00 Petteri Kaski: Parameterization for current and future hardware
Computer hardware is becoming increasingly parallel, hierarchical, and constrained by fundamental physical parameters such as the speed of light and atomic scale. For example, a single high-end compute node today can easily possess more than 10,000 cores, and a leading-edge supercomputer consists of more than 100,000,000 cores with a clock-cycle-length of less than a nanosecond. Algorithm design for such systems must take into account the characteristics of the system and its subsystems via parameters such as capacity, bandwidth, latency, and energy consumption of the different subsystems and their communication-interconnects. This talk looks at the parameters and challenges of current hardware illustrated with examples, and takes a speculative outlook towards the future. For example, we will look at our engineering effort (ALENEX'18) to bring a family of delegatable and error-tolerant "Camelot" algorithms (Björklund & K, PODC'16) arising from Williams' (CCC'16) noninteractive Merlin-Arthur proof systems for batch evaluation from theory to the computing practice. - 12:00 - 13:30 Lunch
- 14:00 - 15:00 Open problem session
- 15:00 - 15:30 Coffee break
- 15:30 - 16:30 Marcin Pilipczuk: Computing sparsity stuff in real world graphs Slides
Graphs of bounded expansion and nowhere dense graphs are robust notions capturing many sparse graph classes. Rich algorithmic theory has been developed in the last decade and recently we have seen a number of experimental works in the area. After a brief survey, I will mostly focus on two primitives in the theory: generalized coloring numbers and the uniform quasi-wideness property from the point of view of algorithmic engineering. Furthermore, we will discuss performance of the algorithms in various real-world graphs (joint work with W. Nadara, R. Rabinovich, F. Reidl, and S. Siebertz, SEA 2018) as well as application of them to kernelization of the dominating set problem (experiments by W. Nadara). - 16:30 - 18:00 Free discussion time
- 18:00 - 19:00 Dinner
Tuesday March 5th, 2019: Kernelization & preprocessing
- 09:00 - 10:00 Darren Strash: Recent advances in kernelization for the maximum independent set problem Slides
In kernelization, a collection of simple rules (called reduction rules) are repeatedly applied to an input instance until the input is reduced to its smallest hardest-to-solve part. Kernelization has long been a powerful technique for developing fixed-parameter tractable algorithms for NP-hard combinatorial problems. Research in the area has exploded in the last 3 years, with a significant number of these results concentrating on the maximum independent set problem. In this talk, we give a thorough overview of the recent theoretical and practical results for this problem, and introduce recent kernelization results for its weighted variant. - 10:00 - 10:30 Coffee break
- 10:30 - 11:00 Sebastian Lamm: A Practical Analysis of Kernelization Techniques for the Maximum Cut Problem Slides
We discuss existing and new kernelization techniques for a well-known NP-Complete problem: Max-Cut. Given an undirected graph, the task here is to find a bipartition of the vertex set that maximizes the total weight of edges that have their endpoints in different partitions. Practical fields for Max-Cut include modeling of social networks, portfolio risk analysis, network design, and statistical physics. We primarily focus on the unweighted case, but we also consider the signed and weighted versions to some degree. Our work heavily focuses on the practical utility of kernelization techniques for Max-Cut. Kernelization techniques compute a smaller problem instance – called a kernel – that if solved allows one to compute a solution for the initially given instance. Our work includes both a theoretical analysis of existing reduction rules as well as the development of brand new ones. Using our set of reduction rules we are able to show that kernelization has a significant impact on a multitude of cases: First, we are able to significantly improve the performance of current state of the art Max-Cut solvers. Second, we are able to solve instances that previously took over 6 hours in just a few seconds. Finally, we are able to compute a maximum cut for instances that were previously infeasible.
Joint work of Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, Darren Strash.
- 11:00 - 11:30 Robert Ganian: The Parameterized Complexity of Matrix Completion Slides
We consider the parameterized complexity of fundamental matrix completion problems, in which we are given a matrix with missing entries and the task is to complete the matrix in a way that optimizes a desired structural measure. In the first part of the talk, we will be focusing on completing the matrix in a way which either minimizes its rank or minimizes the number of distinct rows that appear in the matrix. Afterwards, we will turn our attention to the problem of completing the matrix in order to obtain a clustering of the rows into a small number of clusters, each with small diameter. The presentation will mainly target fixed-parameter algorithms for these problems, showcasing how kernelization and graph-theoretic tools can be used to solve problems which lie outside of the usual frontiers of parameterized complexity.
The talk is based on previously published as well as more recent work with Eduard Eiben, Iyad Kanj, Sebastian Ordyniak and Stefan Szeider.
- 11:30 - 11:40 Group photo
- 12:00 - 13:30 Lunch
- 14:00 - 14:30 Christian Schulz: Shared-Memory Exact Minimum Cuts Slides
The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. We engineer the fastest known exact algorithm for the problem. State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce the graph size such that at least one minimum cut is maintained in the contracted graph. Our algorithm achieves improvements in running time over these algorithms by a multitude of techniques. First, we use a recently developed fast and parallel inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards, we use reductions that depend on this bound to reduce the size of the graph much faster than previously possible. We use improved data structures to further lower the running time of our algorithm. Additionally, we parallelize the contraction routines of Nagamochi et al. . Overall, we arrive at a system that outperforms the fastest state-of-the-art solvers for the exact minimum cut problem significantly. - 14:30 - 15:00 Matthias Bentert: Diameter: A Case Study for FPT in P and the Graph Parameter Hierarchy Slides
Parameterized Algorithmics was introduced to gain practical algorithms for relevant special cases of NP-hard problems; however, the approach is not limited to NP-hard problems. In this talk I will give a brief introduction to the recently advocated research direction of "FPT in P". Afterwards I will present two tools (namely "Graphana" and the "parameter hierarchy") that we are working on and that we believe to be valuable when working with parameterized algorithms (both for NP-hard and polynomial-time solvable problems and for both theoretical and practical work). Finally, I will demonstrate the usefulness of the parameter hierarchy using the polynomial-time solvable problem of computing the diameter of an undirected graph as an example. The overview is based on our paper (https://arxiv.org/abs/1802.10048) and the references therein. - 15:00 - 15:30 Coffee break
- 15:30 - 16:00 Andre Nichterlein: Exact Algorithms for Finding Well-Connected 2-Clubs in Sparse Real-World Graphs: Theory and Experiments Slides
Finding (maximum-cardinality) "cliquish" subgraphs is a central topic in graph mining and community detection. A popular clique relaxation are 2-clubs: instead of asking for subgraphs of diameter one (these are cliques), one asks for subgraphs of diameter at most two (these are 2-clubs). A drawback of the 2-club model is that it produces hub-and-spoke structures (typically star-like) as maximum-cardinality solutions. Hence, we study 2-clubs with the additional constraint to be well-connected. More specifically, we investigate the algorithmic complexity for three variants of well-connected 2-clubs, all established in the literature: robust, hereditary, and "connected" 2-clubs. Finding these more dense 2-clubs is NP-hard; nevertheless, we develop an exact combinatorial algorithm, extensively using efficient data reduction rules. Besides several theoretical insights we provide a number of empirical results based on an engineered implementation of our exact algorithm. In particular, the algorithm significantly outperforms existing algorithms on almost all (sparse) real-world graphs we considered.
The talk is based on joint work with Christian Komusiewicz, Rolf Niedermeier, and Marten Picker.
- 16:00 - 16:30 Henning Meyerhenke: Algorithms and Software for Large and Complex Networked Systems
Motivated by big graph problems, I present a brief overview of the algorithmic research in my group in three application fields: network analysis, combinatorial scientific computing and applied combinatorial optimization for the (life) sciences. - 16:30 - 18:00 Free discussion time
- 18:00 - 19:00 Dinner
Wednesday March 6th, 2019: Integer linear programming & Constraint Satisfaction
- 09:00 - 10:00 Sebastian Ordyniak: Recent Advances on the Parameterized Complexity of Integer Linear Programming Slides
Integer Linear Programming (ILP) is probably the archetypical NP-complete optimisation problem, allowing for the efficient solution of many otherwise intractable optimisation problems in computer science by a translation to ILP. Surprisingly, until very recently, only few tractable classes of ILP had been identified, i.e., ILP is known to be solvable in polynomial-time if the constraint matrix is totally uni-modular (Papadimitriou, Steiglitz 1982) and if the number of variables (or constraints) is constant (Lenstra, 1983). In particular, in contrast to SAT and CSP, ILP had not been studied w.r.t. structural restrictions on the constraint matrix.
The aim of this talk is to survey recent results on the (parameterized) complexity of ILP under structural restrictions on the constraint matrix. Namely, we consider structural restrictions on two graphical models of the constraint matrix (that have had a huge impact for our understanding of SAT and CSP): (1) the primal graph having a vertex for every variable and an edge between every two variables occurring together in a constraint and (2) the incidence graph having a vertex for every variable and every constraint and an edge between a variable and a constraint if the variable occurs (with a non-zero coefficient) in the constraint. After providing an overview about known tractability (and intractability) results w.r.t. well-known decompositional parameters such as treedepth, treewidth, and clique-width, we will show that the well known block-structured ILPs (e.g., n-fold, two-stage stochastic, 4-block N-fold, and tree-fold ILPs) can be modelled (and generalised) in terms of certain structural parameters on the primal and incidence graph.
- 10:00 - 10:30 Coffee break
- 10:30 - 11:30 Gregory Gutin: Theoretical and practical algorithms for CSP parameterized by the number of variables with value-independent constraints
CSP parameterized by the number of variables is W[1]-hard and in W[2]. Fortunately, CSP parameterized by the number of variables with value-independent constraints is FPT and of interest in (security) access control. We'll discuss theoretical results for such a CSP as well as results of computational experiments with FPT algorithms and SAT and CSP solvers.
This is a joint work with Daniel Karapetyan (Essex, UK), Andrew Parkes (Nottingham, UK) and Andrei Gagarin (Cardiff, UK).
- 11:30 - 12:00 Christian Komusiewicz: Towards an efficient implementation of a generic solver for fixed-cardinality optimization in graphs Slides
In fixed-cardinality optimization problems in graphs, we are given a graph $G=(V, E)$, an objective function $f$ , and an integer $k$ and search for a set $S\subseteq V$ of $k$ vertices that maximizes $f(G[S])$. We implement an enumeration-based algorithm for solving fixed-cardinality optimization problems when $G[S]$ needs to be connected. To avoid enumerating all connected subgraphs of order $k$, we present several generic pruning rules. Finally, we perform an experimental analysis of the performance of the algorithm and the usefulness of the pruning rules for eight example problems.
- 12:00 - 13:30 Lunch
- 13:30 - 18:15 Excursion
- 18:15 - 20:15 Main Banquet
Thursday March 7th, 2019: Approaches based on treewidth
- 09:00 - 10:00 Hisao Tamaki: Computing treewidth via exact and heuristic lists of minimal separators Slides
We develop practically efficient algorithms for computing the treewidth tw(G) of a graph G. The core of our approach is a new dynamic programming algorithm which, given a graph G, a positive integer k, and a set Delta of minimal separators of G, decides if G has a tree-decomposition of width at most k of a certain canonical form that uses minimal separators only from Delta, in the sense that the intersection of every pair of adjacent bags belongs to Delta. This algorithm is used to show a lower bound of k + 1 on tw(G), setting Delta to be the set of all minimal separators of cardinality at most k and to show an upper bound of k on tw(G), setting Delta to be some, hopefully rich, set of such minimal separators. Combining this algorithm with new algorithms for exact and heuristic listing of minimal separators, we obtain exact algorithms for treewidth which overwhelmingly outperform previously implemented treewidth algorithms. - 10:00 - 10:30 Coffee break
- 10:30 - 11:00 Yoichi Iwata: Separator-based Pruned Dynamic Programming for Steiner Tree Slides
Steiner tree is a classical NP-hard problem that has been extensively studied both theoretically and empirically. When parameterized by the number of terminals, a dynamic programming algorithm can solve the problem in FPT time. In this talk, I present a novel separator-based pruning technique for speeding up the DP algorithm, which is the key technique used in our winning solver for the PACE challenge 2018. The idea behind our pruning came from a theoretical algorithm for a special case where the graph is planar and all the terminals on a single face. Although this special case is too special to apply in practice, we found that the idea behind this improvement can be used for pruning. Our empirical evaluation shows that our pruned DP algorithm is quite effective against real-world instances admitting small separators, scales to more than a hundred terminals, and is competitive with a branch-and-cut solver. - 11:00 - 11:30 Marcin Pilipczuk: Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation Slides
The notion of treewidth, introduced by Robertson and Seymour in their seminal Graph Minors series, turned out to have tremendous impact on graph algorithmics. Many hard computational problems on graphs turn out to be efficiently solvable in graphs of bounded treewidth: graphs that can be sweeped with separators of bounded size. These efficient algorithms usually follow the dynamic programming paradigm. In the recent years, we have seen a rapid and quite unexpected development of involved techniques for solving various computational problems in graphs of bounded treewidth. One of the most surprising directions is the development of algorithms for connectivity problems that have only single-exponential dependency (i.e., 2^{{O}(t)}) on the treewidth in the running time bound, as opposed to slightly superexponential (i.e., 2^{{O}(t log t)}) stemming from more naive approaches. In this work, we perform a thorough experimental evaluation of these approaches in the context of one of the most classic connectivity problem, namely Hamiltonian Cycle. Joint work with M. Ziobro, presented at SEA 2018. - 12:00 - 13:30 Lunch
- 14:00 - 14:30 Markus Hecher: Projected model counting using small treewidth Slides
We discuss algorithms to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projected variables, where multiple solutions that are identical when restricted to the projected variables count as only one solution. Our algorithm exploits small treewidth of the primal graph of the input instance. It runs in double exponential time in the treewidth and is polynomial in the size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding that the runtime bounds of our algorithm cannot be significantly improved. Finally, we generalize our result to PMC for quantified boolean formulas (QBFs). For solving the decision problem QSAT for QBFs there are already competitive solvers based on treewidth as, e.g., dynqbf. In order to successfully extend dynqbf for counting and solving PMC, we present our idea of practical hybrid parameterized solving. In particular, hybrid solvers aim at leveraging from the interplay between parameterized dynamic programming algorithms and established monolithic solvers. - 14:30 - 15:00 Johannes Fichte: Weighted Model Counting on the GPU by Exploiting Small Treewidth Slides
We propose a novel solver that efficiently finds almost the exact number of solutions of a Boolean formula (#Sat) and the weighted model count of a weighted Boolean formula (WMC) if the treewidth of the given formula is sufficiently small. The basis of our approach are dynamic programming algorithms on tree decompositions, which we engineered towards efficient parallel execution on the GPU. We provide thorough experiments and compare the runtime of our system with state-of-the-art #Sat and WMC solvers. Our results are encouraging in the sense that also complex reasoning problems can be tackled by parameterized algorithms executed on the GPU if instances have treewidth at most 30, which is the case for more than half of counting and weighted counting benchmark instances. In addition, we will present the latest version gpusat2, which uses improved data structures and preprocessing and allows for solving instances up to large treewidth (before reduction). - 15:00 - 15:30 Coffee break
- 15:30 - 16:00 Lukasz Kowalik: From theory to practice in k-OPT heuristic for Travelling Salesman Problem Slides
Given a traveling salesman problem (TSP) tour H in graph G, a k-move is an operation which removes k edges from H, and adds k edges of G so that a new tour H' is formed. The popular k-opt heuristic for TSP finds a local optimum by starting from an arbitrary tour H and then improving it by a sequence of k-moves. In 2016 and 2017 two papers improved the O(n^k) running time of the naive algorithm for finding an improving k-move. I will present the second algorithm, which runs in time O(n^{c_k*k}), where lim c_k = 1/4. While this algorithm, implemented "as is" is unlikely to be useful in practice, I will present a new heuristic based on it, and some preliminary experimental results. Joint work with M. Cygan and K. Zyla. - 16:00 - 18:00 Free discussion time
- 18:00 - 19:00 Dinner
Friday March 8th, 2019: Parameterized algorithms
- Please check out before 10:00
- 09:00 - 10:00 Hans Bodlaender: An ETH-Tight Exact Algorithm for Euclidean TSP Slides
In this talk, we look at the exact complexity of the Euclidean Travelling Salesman Problem; the input for TSP is a set of points in d-dimensional space with Euclidean distances. Assuming the Exponential Time Hypothesis, we settle the asympthotic complexity of this problem, and give an algorithm that runs in 2^O(n^1-1/d) time and show a lowerbound conditional to the ETH of 2^\Omega(n^1-1/d) time, for d>=2. This is joint work with Mark de Berg, Sándor Kisfaludi-Bak and Sudeshna Kolay. - 10:00 - 10:30 Coffee break
- 10:30 - 11:00 Peter Rossmanith: Edge disjoint path packing
Packing edge disjoint paths into a graph is a notoriously complicated problem from a complexity theoretic view. To pack even a single path into a general graph is NP-hard. For k paths the problem is W[1]-hard even on graphs of tree-width two. It becomes fixed parameter tractable on forests and an implementation of this algorithms seems to work well in practice. There is also an algorithm running in time n^O(k^2) for an arbitraty number of paths if the graph has maximal degree bounded by k, at most k components, and at most k vertices with degree higher than two. This running time is almost optimal and the algorithm is practical on small instances. - 11:00 - 11:30 Closing session
- 11:30 - 13:00 Lunch
- 14:00 - 18:00 Free discussion and departure