direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Research Colloquium (Winter Term 2021/2022)

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 tomohiro.koana@tu-berlin.de.

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

Click on rows to expand. The schedule will be updated during the term.
Date Speaker Title
Suhas Thejaswi
(Aalto University, Finland)
Restless reachability problems in temporal graphs

Given a temporal graph and a set of source vertices, we find the set of vertices that are reachable from a source via a time-respecting path, where the difference in timestamps between consecutive edges is at most a resting time. Given a vertex-colored temporal graph and a multiset query of colors, we find the set of vertices reachable from a source via a time-respecting path such that the vertex colors of the path agree with the multiset query and the difference in timestamps between consecutive edges is at most a resting time.

We present an algebraic algorithmic framework based on constrained multilinear sieving for solving the restless reachability problems we propose. In particular, parameterized by the length $k$ of a path sought, we show the problems can be solved in $O(2^k k m \Delta)$ time and $O(n \tau)$ space, where $n$ is the number of vertices, $m$ the number of edges, $\Delta$ the maximum resting time and $\tau$ the maximum timestamp of an input temporal graph. Using a fine-grained evaluation scheme we extend the approach to extract paths and connected subgraphs in both static and temporal graphs, thus improving the work of Bjöklund et al. ~[ESA~2015].

Joint work with Aristides Gionis and Juho Lauri

Philipp Zschoche
(TU Berlin, Germany)
Parameterized Algorithms for Diverse Multistage Problems

The world is rarely static -- many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the "multistage" view on computational problems. We study the "diverse multistage" variant, where consecutive solutions of large variety are preferable to similar ones, e.g. for reasons of fairness or wear minimization. While some aspects of this model have been tackled before, we introduce a framework allowing us to prove that a number of diverse multistage problems are fixed-parameter tractable by diversity, namely Perfect Matching, s-t Path, Matroid Independent Set, and Plurality Voting. This is achieved by first solving special, colored variants of these problems, which might also be of independent interest.

Joint work with Leon Kellerhals and Malte Renken

Tomohiro Koana
(TU Berlin, Germany)
Essentially Tight Kernels for (Weakly) Closed Graphs

We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closure number c and weak closure number γ [Fox et al., SICOMP 2020] in addition to the standard parameter solution size k. The weak closure number γ of a graph is upper-bounded by the minimum of its closure number c and its degeneracy d. For Capacitated Vertex Cover, Connected Vertex Cover, and Induced Matching we obtain the first kernels of size kO(γ), k^O(γ), and (γk)^O(γ), respectively. This extends previous results on the kernelization of these problems on degenerate graphs. These kernels are essentially tight as these problems are unlikely to admit kernels of size k^o(γ) by previous results on their kernelization complexity in degenerate graphs [Cygan et al., ACM TALG 2017]. For Capacitated Vertex Cover, we show that even a kernel of size k^o(c) is unlikely. In contrast, for Connected Vertex Cover, we obtain a problem kernel with O(ck2) vertices. Moreover, we prove that searching for an induced subgraph of order at least k belonging to a hereditary graph class G admits a kernel of size k^O(γ) when G contains all complete and all edgeless graphs. Finally, we provide lower bounds for the kernelization of Independent Set on graphs with constant closure number c and kernels for Dominating Set on weakly closed split graphs and weakly closed bipartite graphs.

Joint work with Christian Komusiewicz and Frank Sommer

Niclas Boehmer
(TU Berlin, Germany)
Line-Up Elections: Parallel Voting with Shared Candidate Pool

We introduce the model of line-up elections which captures parallel or sequential single-winner elections with a shared candidate pool. The goal of a line-up election is to find a high-quality assignment of a set of candidates to a set of positions such that each position is filled by exactly one candidate and each candidate fills at most one position. A score for each candidate-position pair is given as part of the input, which expresses the qualification of the candidate to fill the position. We propose several voting rules for line-up elections and analyze them from an axiomatic and an empirical perspective using real-world data from the popular video game FIFA.

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

Matthias Bentert
(TU Berlin, Germany)
Fairness is Computationally Hard: A Case Study on Shortest Paths

I will talk about a general way of modelling fairness constraints in graph problems using colors. We use shortest s-t-paths as an example and show that requiring a solution to be fair makes the problem NP-hard. This sparked an investigation into the parameterized complexity of the problem where we achieved a quite detailed map of the complexity landscape.

Stanisław Szufa
(Jagiellonian University)
Map of Approval Elections

We present a Map of Approval Elections – a tool that helps in better understanding the nature of approval elections. In particular, we propose new (pseudo)metrics and new statistical models of approval elections. We analyze these models experimentally and use the map to illustrate our results. Moreover, we provide initial results for a Map of Voting Rules, which tries to capture similarities between committees selected by different approval voting rules.

Hendrik Molter
(Ben-Gurion University of the Negev)
Temporal Path Counting

We investigate the problem of computing the number of temporal $(s,z)$-paths in a given temporal graph. This problem is known to be #P-hard and we explore the realm of parameterized and approximate counting algorithms to solve it. The talk will focus on parameterized algorithms.

Temporal path counting is motivated from temporal betweenness computation for optimality concepts such as "foremost" (earliest arrival time) and "fastest" (minimum duration) temporal paths, for which the temporal betweenness computation problem is #P-hard as well.

This is ongoing work with Jessica Enright and Kitty Meeks.

Klaus Heeger
(TU Berlin, Germany)
Popular Matchings with Weighted Voters

In the Popular Matching problem, we are given a bipartite graph $G = (A \cup B, E)$ and for each vertex $v\in A\cup B$, strict preferences over the neighbors of $v$. Given two matchings $M$ and $M'$, matching $M$ is more popular than $M'$ if the number of vertices preferring $M$ to $M'$ is larger than the number of vertices preferring $M'$ to $M$. A matching $M$ is called popular if there is no matching $M'$ that is more popular than $M$.

We consider a natural generalization of Popular Matching where every vertex has a weight. Then, we call a matching $M$ more popular than matching $M'$ if the weight of vertices preferring $M$ to $M'$ is larger than the weight of vertices preferring $M'$ to $M$. For this case, we show that it is NP-hard to find a popular matching. Furthermore, we give a polynomial-time algorithm that delivers a popular matching or a proof for it non-existence in instances where all vertices on one side have weight $c > 3$ and all vertices on the other side have weight 1.

Based on joint work with Ágnes Cseh.

Pascal Kunz
(TU Berlin)
Bipartite Temporal Graphs and the Parameterized Complexity of Multistage 2-Coloring

We consider the algorithmic complexity of recognizing bipartite temporal graphs. Rather than defining these graphs solely by their underlying graph or individual layers, we define a bipartite temporal graph as one in which every layer can be 2-colored in a way that results in few changes between any two consecutive layers. This approach follows the framework of multistage problems that has received a growing amount of attention in recent years. We investigate the complexity of recognizing these graphs. We show that this problem is NP-hard even if there are only two layers or if only one change is allowed between consecutive layers. We consider the parameterized complexity of the problem with respect to several structural graph parameters, which we transfer from the static to the temporal setting in three different ways. Finally, we consider a version of the problem in which we only restrict the total number of changes throughout the lifetime of the graph. We show that this variant is fixed-parameter tractable with respect to the number of changes.

Joint work with Till Fluschnik

Siddharth Gupta
(University of California, Irvine)
Multivariate Analysis of Scheduling Fair Competitions

A fair competition, based on the concept of envy-freeness, is a non-eliminating competition where each contestant (team or individual player) may not play against all other contestants, but the total difficulty for each contestant is the same: the sum of the initial rankings of the opponents for each contestant is the same. Similar to other non-eliminating competitions like the Round-robin competition or the Swiss-system competition, the winner of the fair competition is the contestant who wins the most games. The Fair Non-Eliminating Tournament (Fair-NET) problem can be used to schedule fair competitions whose infrastructure is known. In the Fair-NET problem, we are given an infrastructure of a tournament represented by a graph G and the initial rankings of the contestants represented by a multiset of integers S. The objective is to decide whether G is S-fair, i.e., there exists an assignment of the contestants to the vertices of G such that the sum of the rankings of the neighbors of each contestant in G is the same constant k. We initiate a study of the classical and parameterized complexity of Fair-NET with respect to several central structural parameters motivated by real world scenarios, thereby presenting a comprehensive picture of it.

Joint work with Meirav Zehavi.

Ulrike Schmidt-Kraepelin
(TU Berlin)
The popular assignment problem: when cardinality is more important than popularity

We consider a matching problem in a bipartite graph $G=(A \cup B,E)$ where each node in $A$ is an agent having preferences in partial order over her neighbors, while nodes in $B$ are objects with no preferences. The size of our matching is more important than node preferences; thus, we are interested in maximum matchings only. Any pair of maximum matchings in $G$ (equivalently, perfect matchings or assignments) can be compared by holding a head-to-head election between them where agents are voters. The goal is to compute an assignment $M$ such that there is no better or "more popular" assignment. This is the popular assignment problem and it generalizes the well-studied popular matching problem. Popular assignments need not always exist. We show a polynomial-time algorithm that decides if the given instance admits one or not, and computes one, if so. In instances with no popular assignment, we consider the problem of finding an almost popular assignment, i.e., an assignment with minimum unpopularity margin. We show an $O^*(|E|^k)$ time algorithm for deciding if there exists an assignment with unpopularity margin at most k. We show that this algorithm is essentially optimal by proving that the problem is $W_l[1]$-hard with parameter $k$. We also consider the minimum-cost popular assignment problem when there are edge costs, and show its 𝖭𝖯-hardness even when all edge costs are in $\{0,1\}$ and agents have strict preferences. By contrast, we propose a polynomial-time algorithm to the problem of deciding if there exists a popular assignment with a given set of forced/forbidden edges (this tractability holds even for partially ordered preferences). Our algorithms are combinatorial and based on LP duality. They search for an appropriate witness or dual certificate, and when a certificate cannot be found, we prove that the desired assignment does not exist in $G$.

Joint work with Telikepalli Kavitha, Tamás Király, Jannik Matuschke, Ildikó Schlotter

Frank Sommer
(Philipps-Universität Marburg)
Parameterized Complexity and Algorithm Engineering for s-Club with Triangle and Seed Constraints

The s-Club problem asks, for a given undirected graph G, whether G contains a vertex set S of size at least k such that G[S], the subgraph of G induced by S, has diameter at most s. We consider variants of s-Club where one additionally demands that each vertex is contained in at least \ell triangles, that each edge is contained in at least \ell triangles, or that S contains a given set W of seed vertices. We show that in general these variants are W[1]-hard when parameterized by the solution size k, making them significantly harder than the unconstrained s-Club problem. Furthermore, we implement an exact solver for s-Club with triangle constraints and evaluate its performance on many real-world instances.

This is joint work with Jaroslav Garvardt, Niels Grüttemeier, Philipp Heinrich Keßler, and Christian Komusiewicz.

Malte Renken
(TU Berlin)
Delay-Robust Routes in Temporal Graphs

Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable — in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are robust to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.

This is joint work with Eugen Füchsle, Hendrik Molter, Rolf Niedermeier.

Arindam Biswas
(TU Ilmenau)
Sublinear-Space Approximation Algorithms for Hitting Set

Over the years, much research has been conducted on ways of dealing with the apparent intractability of NP-hard problems. The two most well known frameworks utilized to this end are approximation and parameterization.

Common examples of approximation or parameterized algorithms use amounts of work memory that are polynomial in the input sizes. This is not unreasonable, when one observes that it becomes difficult to perform (in polynomial time) primitive operations on graphs such as computing breadth-first traversals or maximal independent sets, when one only has sublinear amounts of work memory available. In fact, certain order-dependent variants of these primitives are known to be P-complete to compute, giving an indication that it should be hard to carry them out in polylogarithmic space space and polynomial time.

In this talk, we show that one can devise approximation algorithms for certain restrictions of HITTING SET which run in (close to) logarithmic space and polynomial time. We look at the following algorithms. - An O(dδ log n)-space n^{O(dδ)}-time d-approximation algorithm for HITTING SET restricted to sets of size at most d and element multiplicity δ. - A O((d² + (d/ε)) log n)-space n^{O(d² + (d/ε))}-time ((d/ε) n^ε)-approximation scheme for HITTING SET restricted to sets of size at most d.

Leon Kellerhals
(TU Berlin)
Modification-Fair Cluster Editing

The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge modifications. When applied to vertex-colored graphs (the colors representing subgroups), standard algorithms for the NP-hard Cluster Editing problem may yield solutions that are biased towards subgroups of data (e.g., demographic groups), measured in the number of modifications incident to the members of the subgroups. We propose a modification fairness constraint which ensures that the number of edits incident to each subgroup is proportional to its size. To start with, we study Modification-Fair Cluster Editing for graphs with two vertex colors. We show that the problem is NP-hard even if one may only insert edges within a subgroup; note that in the classic "non-fair" setting, this case is trivially polynomial-time solvable. However, in the more general editing form, the modification-fair variant remains fixed-parameter tractable with respect to the number of edge edits. We complement these and further theoretical results with an empirical analysis of our model on real-world social networks where we find that the price of modification-fairness is surprisingly low, that is, the cost of optimal modification-fair differs from the cost of optimal "non-fair" solutions only by a small percentage.

Zusatzinformationen / Extras