Description
Talk #1: Alexander Göke
Title: Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
Abstract: The Directed Feedback Vertex Set (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing pen problem until Chen et al. [STOC 2008, J. ACM 2008] showed its fixed-parameter tractability via a 4^k k!n^{O(1)} -time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS:
- Find a smallest vertex set S such that every strong component of G−S has size at most s: we give an algorithm solving this problem in time 4^k (ks+k+s)!n^{O(1)}. This generalizes an algorithm by Xiao [JCSS 88, pp. 260-270, 2017] for the undirected version of he problem.
- Find a smallest vertex set S such that every non-trivial strong component of G − S is 1-out-regular: we give an algorithm solving this problem in time 2^{O(k^3)} n^{O(1)}.We also solve the corresponding arc versions of these problems by fixed-parameter algorithms.
----------------------------
Talk #2: Simon Omlor
Title: Faster Algorithms for Machine Scheduling
Abstract: Non-preemptive scheduling of jobs on machines is a fundamental task in combinatorial optimization. Here one has to assign each of n jobs to one of m machines, so as to optimize an overall objective: minimizing the makespan, maximizing the minimum machine load, inimizing the envy, or minimizing the sum of convex functions of machine completion times.In this work we obtain strong combinatorial characterizations of optimal solutions to these basic problems, which lead to fast exact algorithms for instances with d distinct job types and largest processing time \Delta :
- For parallel machines, we find optimal schedules for various objective functions in time \Delta^{O(d)} * \log(n); this improves the previous best algorithm by Knop et al. [ESA 2017] with run time \Delta^O(d^2) * \log(n).
- For parallel machines with k distinct job release times and deadlines, we find makespan-minimizing schedules in time (\Delta d)^{O(kd)} * \log(n).
- For related machines of s different speeds of ratio \beta = s_max /s_min, we find makespan-minimizing schedules in time (\Delta\beta)^{O(d+s)} * \log(n).
- For unrelated machines with inclusive or nested processing set restrictions with k different processing sets and service ratio \eta, we find optimal schedules for various objective functions in time (ηk\Delta)^{O(kd)} * \log(n).
--------------------------
Talk #3: Roland Vincze
Title: Time- and space-optimal algorithms for the many-visits TSP
Abstract: The many-visits traveling salesperson problem (MV-TSP) asks for an optimal tour of n cities that visits each city c a prescribed number kc of times. Travel costs may not be symmetric, and visiting a city twice in a row may incur a non-zero cost. The MV-TSP problem finds applications in scheduling, geometric approximation, and Hamiltonicity of certain graph families. The fastest known algorithm for MV-TSP is due to Cosmadakis and Papadimitriou (SICOMP, 1984). It runs in time n^{O(n)}+O(n^3\log \sum_ck_c)and requires n^{Ω(n)} space. The interesting feature of the Cosmadakis-Papadimitriou algorithm is its logarithmic dependence on the total length \sum_ck_c of the tour, allowing the algorithm to handle instances with very long tours, beyond what is tractable in the standard TSP setting. However, the superexponential dependence on the number of cities in both its time and space complexity renders the algorithm impractical for all but the narrowest range of this parameter.
We significantly improve on the Cosmadakis-Papadimitriou algorithm, giving an MV-TSP algorithm that runs in single-exponential time with output-linear space. More precisely, we obtain the running time 2^{O(n)}+O(n^3\log \sum_ck_c), with O(n^2\log \sum_c k_c) space.Assuming the Exponential-time Hypothesis (ETH), both the time and space requirements of our algorithm are optimal. Our algorithm is deterministic, and arguably both simpler and easier to analyse than the original approach of Cosmadakis and Papadimitriou.
--------------------------
Talk #4: Matthias Mnich
Title: Odd Multiway Cut in Directed Acyclic Graphs
Abstract: We investigate the odd multiway node (edge) cut problem where the input is a graph with a specified collection of terminal nodes and the goal is to find a smallest subset of nonterminal nodes (edges) to delete so that the terminal nodes do not have an odd length path between them. In an earlier work, Lokshtanov and Ramanujan showed that both odd multiway node cut and odd multiway edge cut are fixed-parameter tractable (FPT) when parameterized by the size of the solution in undirected graphs. In this work, we focus on directed acyclic graphs (DAGs) and design a fixed-parameter algorithm. Our main contribution is a broadening of the shadow-removal framework to address parity problems in DAGs. We complement our FPT results with tight approximability as well as polyhedral results for 2 terminals in DAGs. Additionally, we show inapproximability results for odd multiway edge cut in undirected graphs even for 2 terminals.