TU Berlin

Algorithmics and Computational Complexity Research GroupSummer Term 2021



zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Research Colloquium (Summer Term 2021)

The research colloquium "Algorithmik und Komplexitätstheorie" provides talks of external guests, members of the research staff, Ph.D. students, and advanced students (theses) about recent results and research topics in theoretical computer science and related areas. The core areas are algorithmics and computational complexity theory. If you would like to receive information about upcoming talks, please join our mailing list. If you would like to give a talk yourself, feel free to send an email to m.renken@tu-berlin.de.

Due to the Coronavirus situation, this semester’s talks are given online, usually at https://tu-berlin.zoom.us/j/68424360050?pwd=a2F3TlV4bzZPckxwOStOWkR4NzhuQT09.

Click on rows to expand. The schedule will be updated during the term.
Date Speaker Title
Matthias Bentert
(TU Berlin)
Using a geometric lens to find k disjoint shortest paths.

Given an undirected n-vertex graph and k pairs of terminal vertices $(s_1,t_1),…,(s_k,t_k)$, the k-Disjoint Shortest Paths (k-DSP)-problem asks whether there are k pairwise vertex-disjoint paths $P_1,…,P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i∈[k]$. Recently, Lochet [arXiv 2019] provided an algorithm that solves k-DSP in $n^{O(k^{4^k})}$ time, answering a 20-year old question about the computational complexity of k-DSP for constant k.

On the one hand, we present an improved $O(k⋅n^{{12k⋅k!+k+1}})$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$, we show that the running time can be further reduced to $O(n^2⋅m)$ by small modifications of the algorithm and a further refined analysis. On the other hand, we show that k-DSP is W[1]-hard with respect to k, showing that the dependency of the degree of the polynomial running time on the parameter k is presumably unavoidable.

Christoph Hertrich
(TU Berlin)
Complexity of ReLU Neural Network Training Parameterized by Data Dimensionality

Training a neural network, that is, minimizing a loss function on a finite dataset, is the crucial step of many machine learning algorithms. A large variety of hardness results has been established for this problem and practitioners usually use heuristic methods. We analyze the computational complexity of this problem from a parameterized point of view with respect to the dimension of the training data. Focusing on $\ell^p$ losses, we show that, for $p \in [0, \infty[$, already training a one-node neural network is W[1]-hard and known brute-force strategies are essentially optimal (assuming the Exponential Time Hypothesis). Matching these lower bounds, we extend a known XP-algorithm to all these loss functions and observe that, for $p=\infty$, there exists a polynomial time algorithm.

This is joint work with Vincent Froese and Rolf Niedermeier.

Leon Kellerhals
(TU Berlin)
Placing Green Bridges Optimally, with a Multivariate Analysis.

We study the problem of placing wildlife crossings, such as green bridges, over human-made obstacles to challenge habitat fragmentation. The main task herein is, given a graph describing habitats or routes of wildlife animals and possibilities of building green bridges, to find a low-cost placement of green bridges that connects the habitats. We develop three problem models for this task, which model different ways of how animals roam their habitats. We settle the classical complexity and parameterized complexity (regarding the number of green bridges and the number of habitats) of the three problems.

This is joint work with Till Fluschnik.

Niclas Boehmer
(TU Berlin)
Winner Robustness via Swap-Bribery: Parameterized Counting Complexity and Experiments

In Swap-Bribery, we are given an election, a designated candidate, and a budget k and the task is to decide whether it is possible to modify the election by swapping at most k adjacent candidates in some of the votes such that the designated candidate becomes a winner of the election. We study the (parameterized) complexity of counting variants of Swap-Bribery, focusing on the parameterizations by the number of swaps and the number of voters. Facing several computational hardness results, using sampling we show experimentally that counting variants of Swap-Bribery offer a new approach to the robustness analysis of elections.

This is joint work with Robert Bredereck, Piotr Faliszewski, and Rolf Niedermeier.

Tomohiro Koana
(TU Berlin)
The Complexity of Gerrymandering Over Graphs: Paths and Trees

Roughly speaking, gerrymandering is the systematic manipulation of the boundaries of electoral districts to make a specific (political) party win as many districts as possible. While typically studied from a geographical point of view, addressing social network structures, the investigation of gerrymandering over graphs was recently initiated by Cohen-Zemach et al. [AAMAS 2018]. Settling three open questions of Ito et al. [AAMAS 2019], we classify the computational complexity of the NP-hard problem Gerrymandering over Graphs when restricted to paths and trees. Our results, which are mostly of negative nature (that is, worst-case hardness), in particular yield two complexity dichotomies for trees. For instance, the problem is polynomial-time solvable for two parties but becomes weakly NP-hard for three. Moreover, we show that the problem remains NP-hard even when the input graph is a path.

André Nichterlein
(TU Berlin)
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the allowed editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the allowed editing operations are vertex deletions).

Answering an open question from the literature, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, clearly outperforming a standard CPLEX solver in most instances of an established biological test data set.

Joint work with Aleksander Figiel, Anne-Sophie Himmel, and Rolf Niedermeier.

Esther Ulitzsch
(IPN Kiel)
Understanding Response Processes in Interactive Assessments via Graph-based Data Clustering: Method Development, Applications, and Open Questions

Educational large-scale assessments such as the Programme for International Student Assessment (PISA) or the International Assessment of Adult Competencies (PIAAC) aim at measuring what examinees know and can do. In recent years, large-scale assessment moved from paper-and-pencil-based multiple-choice items to computer-administered complex interactive tasks. Assessments using interactive tasks allow logging time-stamped action sequences. These sequences pose a rich source of information that supports moving from investigating from whether to how examinees solved a given task.

We provide an approach that leverages time-stamped action sequence data for identifying common response processes, i.e., groups of examinees that approached the tasks in a comparable manner. In doing so, we integrate tools from clickstream analyses and graph-modeled data clustering with psychometrics. In our approach, we (a) provide similarity measures that are based on both actions and the associated action-level timing data and (b) subsequently employ cluster edge deletion for identifying homogeneous, interpretable, well-separated groups of time-stamped action sequences, each describing a common response process. The approach and its utility are illustrated on a complex problem-solving task from PIAAC 2012. Open questions concerning the validity and scalability of the procedure are discussed.

Joint work with Qiwei He, Vincent Ulitzsch, Hendrik Molter, André Nichterlein, Rolf Niedermeier \& Steffi Pohl.

Till Fluschnik
(TU Berlin)
Feedback Vertex Set and 3-Coloring on Hamiltonian Graphs

We study the computational complexity of Feedback Vertex Set and 3-Coloring on subclasses of Hamiltonian graphs, also when a Hamiltonian cycle is additionally given as part of the input. We consider Hamiltonian graphs that are regular, or are planar and regular, or fall into the less known class of p-(Hamiltonian-)ordered graphs, which are graphs that admit for any p-tuple of vertices a (Hamiltonian) cycle visiting them in the order given by the tuple.

This is joint work with Dario Cavallaro.

Wolfgang Hönig
(TU Berlin)
Multi-Agent Path Finding (MAPF): Variants, Algorithms, and Applications in Robotics

Multi-Agent Path Finding (or short MAPF) is the following NP-hard problem: Given a graph, N start vertices, and N goal vertices, find collision-free paths for N agents that move on the graph such that the sum-of-cost is minimized. While MAPF is an interesting problem theoretically, it has also found many applications in traffic control, autonomous vehicles, and robotics. These applications have inspired novel problem variants of MAPF. I will present major variants, their complexity, optimal/bounded suboptimal/suboptimal algorithms to solve them, and solutions to use the results in robotic applications.

This talk is aimed to be an introduction/tutorial on MAPF.

Benjamin Bumpus
(University of Glasgow)
Spined Categories: generalising tree-width beyond graphs

Problems that are NP-hard in general are often tractable on inputs that have a recursive structure. For instance consider classes defined in terms of `graph decompositions’ such as of bounded tree- or clique-width graphs. Given the algorithmic success of graph decompositions, it is natural to seek analogues of these notions in other settings. What should a `tree-width-k’ digraph or lattice or temporal graph even look like?

Since most decomposition notions are defined in terms of the internal structure of the decomposed object, generalizing a given notion of decomposition to a larger class of objects tends to be an arduous task. In this talk I will show how this difficulty can be reduced significantly by finding a characteristic property formulated purely in terms of the category that the decomposed objects inhabit, which defines the decomposition independently of the internal structure.

I will introduce an abstract characterisation of tree-width as a vast generalisation of Halin’s definition of tree-width as the maximal graph parameter sharing certain properties with the Hadwiger number and chromatic number. Our uniform construction of tree-width provides a roadmap to the discovery of new tree-width-like parameters simply by collecting the relevant objects into our new notion of a spined category.

This is joint work with Zoltan A. Kocsis (University of New South Wales).

Malte Renken
(TU Berlin)
Temporal Reachability Minimization

We study spreading processes in temporal graphs, i. e., graphs whose connections change over time. These processes naturally model real-world phenomena such as infectious diseases or information flows. More precisely, we investigate how such a spreading process, emerging from a given set of sources, can be contained to a small part of the graph. To this end we consider two ways of modifying the graph, which are (1) deleting connections and (2) delaying connections. We show a close relationship between the two associated problems and give a polynomial time algorithm when the graph has tree structure. For the general version, we consider parameterization by the number of vertices to which the spread is contained. Surprisingly, we prove W[1]-hardness for the deletion variant but fixed-parameter tractability for the delaying variant.

Joint work with Hendrik Molter and Philipp Zschoche.

Klaus Heeger
(TU Berlin)
Bribery and Control in Stable Marriage

We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter ``budget'' (that is, the number of manipulative actions one is allowed to perform), we also conduct a parameterized complexity analysis and encounter mostly parameterized hardness results.

Based on joint work with Niclas Boehmer, Robert Bredereck, and Rolf Niedermeier.

Malte Renken
(TU Berlin)
Git for writing papers: beyond `git commit -a; git pull; git push`

A small tutorial on the workings of git with a focus on LaTeX documents.



Schnellnavigation zur Seite über Nummerneingabe