Algorithmics and Computational Complexity

## Research Colloquium

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(dot)koana(at)tu-berlin.de.

## Induced Matching below Guarantees: Average Paves the Way for Fixed-Parameter Tractability

In this work, we study the Induced Matching problem: Given an undirected graph G and an integer l, is there an induced matching M of size at least l? An edge subset M is an induced matching in G if M is a matching such that there is no edge between two distinct edges of M. Our work looks into the parameterized complexity of Induced Matching with respect to “below guarantee” parameterizations. We consider the parameterization u − l for an upper bound u on the size of any induced matching. For instance, any induced matching is of size at most n/2 where n is the number of vertices, which gives us a parameter n/2 − l. In fact, there is a straightforward 9n/2−l · nO(1)-time algorithm for Induced Matching [Moser and Thilikos, J. Discrete Algorithms]. Motivated by this, we ask: Is Induced Matching FPT for a parameter smaller than n/2 − l? In search for such parameters, we consider MM(G) − l and IS(G) − l, where MM(G) is the maximum matching size and IS(G) is the maximum independent set size of G. We find that Induced Matching is presumably not FPT when parameterized by MM(G) − l or IS(G) − l. In contrast to these intractability results, we find that taking the average of the two helps—our main result is a branching algorithm that solves Induced Matching in 49(MM(G)+IS(G))/2−l · nO(1) time. Our algorithm makes use of the Gallai–Edmonds decomposition to find a structure to branch on.

## An introduction to streaming algorithms.

Streaming algorithms are used in a big data context, where data does not fit into main memory and the use of external memory is too slow to keep up with the speed of arriving new input data. Streaming algorithms are allowed to read the input once and use sublinear (ideally polylogarithmic) memory. From a theoretical point of view, the streaming model is interesting since one can often show unconditional linear lower bounds for the memory requirements of solving problems, which can then be surprisingly effectively broken through using randomization or approximation approaches, which make apparently unsolvable problems solvable. The lecture gives an introduction to the streaming model, its applications, basic lower bounds, algorithms for reconstructing frequency vectors, and their applications to solving graph problems in the model where a graph is given as a stream of edge insertions and deletions.

## Locality in online, dynamic, sequential, and distributed graph algorithms

In this talk, I will introduce a new online model of computing for graph problems, called online-LOCAL. In this model, the adversary reveals the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each new node the algorithm can also inspect its radius-T neighborhood before choosing the output. Instead of looking ahead in time, we have the power of looking around in space. This model gives a unifying view of locality in four settings: LOCAL model of distributed computing, its sequential counterpart SLOCAL, dynamic algorithms, and online algorithms.

We show that for LCL problems in paths, cycles, and rooted trees, all four models are roughly equivalent: the locality of any LCL problem falls in the same broad class - O(log∗ n), Θ(log n), or n^Θ(1) - in all four models. In particular, prior work on the LOCAL model directly generalizes to all four models.

Second, we show that this equivalence does not hold in two-dimensional grids. We show that the locality of the 3-coloring problem is O(log n) in the online-LOCAL model, while it is Ω(√n) in the SLOCAL model.

This talk is based on joint work with Amirreza Akbari, Navid Eslami, Henrik Lievonen, Joona Särkijärvi, and Jukka Suomela, and there is a manuscript available at https://arxiv.org/abs/2109.06593

## Tree Containment with respect to Treewidth and Scanwidth.

In the TREE CONTAINMENT problem, we are given a phylogenetic network (rooted leaf-labeled DAGs in which every vertex has in-degree or out-degree at most one) and a phylogenetic tree (rooted leaf-labeled out-branchings) and the task is to find an embedding of the tree in the network. This problem is NP-hard even for the biologically meaningful case that the maximum degree in both the network and the tree is three. Although the related DISJOINT PATHS problem can be solved in O*(2^w log w) time on graphs of treewidth w (and not asymptotically better, assuming ETH), the algorithm can not be easily adapted for the TREE CONTAINMENT problem. We present an O*(2^w^2)-time algorithm for the latter problem as well as an O*(2^s log s)-time algorithm where s is the (slightly weaker parameter) "scanwidth" of the input network.

## A Map of Diverse Synthetic Stable Roommates Instances

Focusing on Stable Roommates (SR) instances, we contribute to the toolbox for conducting experiments for stable matching problems. We introduce the polynomial-time computable mutual attraction distance to measure the similarity of SR instances, analyze its properties, and use it to create a map of SR instances. This map visualizes 460 synthetic SR instances (each sampled from one of ten different statistical cultures) as follows: Each instance is a point in the plane, and two points are close on the map if the corresponding SR instances are similar to each other. Subsequently, we conduct several exemplary experiments and depict their results on the map, illustrating the map's usefulness as a non-aggregate visualization tool, the diversity of our generated dataset, and the need to use instances sampled from different statistical cultures.

This is joint work with Klaus Heeger and Stanisław Szufa.

## Parameterized Algorithms for Colored Clustering.

In the COLORED CLUSTERING problem, one is asked to cluster edge-colored (hyper-)graphs whose colors represent inter- action types. The goal is to place the vertices into groups that frequently participate in the same type of interaction. More specifically, the goal is to select as many edges as possible without choosing two edges that both share an endpoint and are colored differently. Equivalently, the goal can also be described as assigning colors to the vertices in a way that fits the edge-coloring as well as possible. As this problem is NP-hard, we build on previous work by studying its parameterized complexity. We give a 2^O(k) n^O(1)-time algorithm where k is the number of edges to be selected and n the number of vertices. We also prove the existence of a problem kernel of size O(k^5/2), resolving an open problem posed in the literature. We consider parameters that are smaller than k, the number of edges to be selected, and r, the number of edges that can be deleted. Such smaller parameters are obtained by considering the difference between k or r and some lower bound on these values. We give both algorithms and lower bounds for COLORED CLUSTERING with such parameterizations. Finally, we settle the parameterized complexity of COLORED CLUSTERING with respect to structural graph parameters by showing that it is W[1]-hard with respect to both vertex cover number and tree-cut width, but fixed-parameter tractable with respect to local feedback edge number.

Joint work with Leon Kellerhals, Tomohiro Koana, and Rolf Niedermeier

## Graph width parameters in RNA bioinformatics.

RNA molecules consist of chains of individual blocks called nucleotides (A, U, G, C), and perform a wide variety of functions in biological systems. These functions critically depend on the 3D structures adopted by these molecules, i.e. the way nucleotides are paired up in complex folding conformations.

Several natural computational problems  involving this structure then emerge, such as folding (what is the preferred structure of an RNA sequence ?) or structure reconfiguration (is there a feasible reconfiguration path between these two structures ?). These problems are typically computationally hard, especially when going towards realistic biological models.

This talk will focus on selected instances of such landmark problems, and on current attempts to tackle them with exact parameterized algorithmics. A particular focus will be given to graph algorithms, and graph width parameters. Examples of graph problems emerging from this angle include minimum edge deletion towards a target treewidth value [1], or the computation of directed pathwidth for a particular geometric subset of directed graphs [2].

References:
[1] B. Marchand, Y. Ponty, L. Bulteau. Tree Diet: Reducing the Treewidth to Unlock FPT Algorithms in RNA Bioinformatics. Algorithms for Molecular Biology 2022.
[2] L. Bulteau, B. Marchand, Y. Ponty. A new parameterization for independent set reconfiguration and applications to RNA kinetics. IPEC 2021.

## Temporal Voronoi games.

We study Voronoi games in temporal graphs with a focus on the existence of Nash equilibria in trees and cycles.

## Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems.

When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.

Joint work with Niclas Boehmer and Rolf Niedermeier.

## Correlating Theory and Practice in Finding Clubs and Plexes

Finding large “cliquish" subgraphs is a classic NP-hard graph problem. In this work, we focus on finding maximum s-clubs and s-plexes, i. e., graphs of diameter s and graphs where each vertex is adjacent to all but s vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a new parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we provide evidence that the new theoretical bounds indeed better explain the observed running times than the existing theoretical running time bounds. To this end, we suggest a general method to compare how well theoretical running time bounds fit to measured running times.

Joint work with Aleksander Figiel, Tomohiro Koana, Niklas Wünsche

## Vertex Cover and Feedback Vertex Set Above and Below Structural Guarantees

Vertex Cover parameterized by the solution size k is the quintessential fixed-parameter tractable problem. FPT algorithms are most interesting when the parameter is small. Several lower bounds on k are well-known, such as the maximum size of a matching. This has led to a line of research on parameterizations of Vertex Cover by the difference of the solution size k and a lower bound. The most prominent cases for such lower bounds for which the problem is FPT are the matching number or the optimal fractional LP solution. We investigate parameterizations by the difference between k and other graph parameters including the feedback vertex number, the degeneracy, cluster deletion number, and treewidth with the goal of finding the border of fixed-parameter tractability for said difference parameterizations. We also consider similar parameterizations of the Feedback Vertex Set problem.

Joint work with Leon Kellerhals and Pascal Kunz