#### Geometric Heuristics for Rectilinear Crossing Minimization

Radermacher, Marcel; Reichard, Klara; Rutter, Ignaz; Wagner, DorotheaAbstract. Five new algorithms, named Vsep, are described. Four of them are for determining the generators, orbits and order of the graph automorphism group. The fifth algorithm is for finding an isomorphism between two graphs. A basic tool of these algorithms is an iterative adjacency refinement procedure that produces finer output partition from a given input partition of graph vertices. All nonequivalent discrete partitions derived from the selected vertices are stored. This is the main difference of the exact version with the known algorithms for graph automorphism group. A new strategy is used in the exact algorithm: if during its execution some of the searched or intermediate variables obtain a wrong value then the algorithm continues from a new start point losing some of the results determined so far. The new start point is such that the correct results are obtained. The proposed algorithms have been tested on well-known benchmark graphs and compared with one of the most competitive known tool for the worst cases (Traces). The results show that for some graph families the exact Vsep algorithm outperforms Traces, and vice-versa for some of the others. The heuristic versions use reduced search trees. They are almost exact and are many times faster than the exact one. The heuristic algorithms are a good choice for the user because of their smaller running times. The experiments show that the running time of Vsep algorithms does not depend on the vertex labeling.

We introduce the adaptive cuckoo filter (ACF), a data structure for approximate set membership that extends cuckoo filters by reacting to false positives, removing them for future queries. As an example application, in packet processing queries may correspond to flow identifiers, so a search for an element is likely to be followed by repeated searches for that element. Removing false positives can therefore significantly lower the false positive rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store fingerprints. We allow fingerprint entries to be changed in response to a false positive in a manner designed to minimize the effect on the performance of the filter. We show that the ACF is able to significantly reduce the false positive rate by presenting both a theoretical model for the false positive rate and simulations using both synthetic data sets and real packet traces.

*k*-Plexes in Temporal Graphs Matthias Bentert (Technische Universitat Berlin); Anne-Sophie Himmel (Technische Universitat Berlin); Hendrik Molter (Technische Universitat Berlin); Marco Morik (Technische Universitat Berlin); Rolf Niedermeier (Technische Universitat Berlin); RenĂ© Saitenmacher (Technische Universitat Berlin)

Many real-world networks evolve over time, that is, new contacts appear and old contacts may disappear. They can be modeled as temporal graphs where interactions between vertices (which represent people in the case of social networks) are represented by time-stamped edges. One of the most fundamental problems in (social) network analysis is community detection, and one of the most basic primitives to model a community is a clique.
Addressing the problem of finding communities in temporal networks, Viard et al. [TCS 2016] introduced ?-cliques as a natural temporal version of cliques. Himmel et al. [SNAM 2017] showed how to adapt the well-known Bron-Kerbosch algorithm to enumerate ?-cliques. We continue this work and improve and extend the algorithm of Himmel et al. to enumerate temporal *k*-plexes (notably, cliques are the special case *k*=1).
We define a ?-*k*-plex as a set of vertices with a lifetime, where during the lifetime each vertex has in each consecutive ?+1 time steps edges to all but at most *k*-1 vertices in the chosen set of vertices.
We develop a recursive algorithm for enumerating all maximal ?-*k*-plexes and perform experiments on real-world social networks that demonstrate the practical feasibility of our approach. In particular, for the special case of ?-1-plexes (that is, ?-cliques), we observe that our algorithm is on average significantly faster than the previous algorithms by Himmel et al. [SNAM 2017] and Viard et al. [IPL 2018] for enumerating ?-cliques.

We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a k-way partition. The framework generalizes the flow-based improvement algorithm of KaFFPa from graphs to hypergraphs and is integrated into the hypergraph partitioner KaHyPar. By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas for both the connectivity and the cut-net metric while still having a running time comparable to that of hMetis. In the case of graph partitioning, our algorithm compares favorably with KaFFPa, even after enhancing the latter with our improved flow network, and at the same time is more than a factor of two faster. Finally, we show that our algorithm improves the performance of the memetic multilevel hypergraph partitioner KaHyPar-E.

In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying so-called n-fold integer programming. An n-fold integer program (IP) has a highly uniform block structured constraint matrix. Hemmecke et al. [Math. Programming, 2013] showed an algorithm with runtime \Delta^O(rst+r^2s)n^3, where \Delta is the largest coefficient, r,s, and t are dimensions of blocks of the constraint matrix and n is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and n-fold IPs have the property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. We have implemented the algorithm and learned the following. The original algorithm is practically unusable, but a series of improvements make its evaluation possible. Crucially, a certain constant in the algorithm can be treated as a tuning parameter, yielding an efficient heuristic. Furthermore, the algorithm uses an overly expensive strategy to find a "best" step, while finding only an "approximatelly best" step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on n from n^3 to n^2log(n). We show that decreasing the tuning parameter initially leads to an increased number of iterations needed for optimality and eventually to local optima, as expected. However, surprisingly small values of the parameter are often enough. Second, our new strategy for finding "approximatelly best" steps wildly outperforms the original construction.

We study dynamic graphs in the fully-dynamic {centralized} setting. In this setting the vertex set of size $n$ of a graph $G$ is fixed, and the edge set changes step-by-step, such that each step either adds or removes an edge. Dynamic graphs have various applications in fields such as Communication Networks, Computer Graphics and VLSI Design. The goal in this setting is maintaining a solution to a certain problem (e.g., maximal matching, edge coloring) after each step, such that each step is executed efficiently. The running time of a step is called {\em update-time}. Prior to the current work, for several central problems, the best known deterministic algorithms for general graphs were the naive ones with update-time O(n). The question of existence of sublinear in $n$ update-time deterministic algorithms remained wide open. In this paper we address this question by devising sublinear update-time deterministic algorithms for maximal matching in graphs with bounded neighborhood independence o(n/ \log^2 n)}, and for proper O(\Delta)-edge-coloring in {general graphs}. The family of graphs with bounded neighborhood independence is a very wide family of dense graphs, and represent very well various types of networks. In order to obtain our results we employ a novel approach that adapts certain distributed algorithms of the { LOCAL} setting to the centralized fully-dynamic setting. This is achieved by optimizing the work each processors performs, and efficiently simulating a distributed algorithm in a centralized setting. Our experiments on various network topologies and scenarios demonstrate that our algorithms are highly-efficient in practice.

Clustering is a fundamental problem in data science, yet, the variety of clustering methods and their sensitivity to parameters make clustering hard. To analyze the stability of a given clustering algorithm while varying its parameters, and to compare clusters yielded by different algorithms, several comparison schemes based on matchings, information theory and various indices (Rand, Jaccard) have been developed. We go beyond these by providing a novel class of methods computing meta-clusters within each clustering? a meta-cluster is a group of clusters, together with a matching between these. Let the intersection graph of two clusterings be the edge-weighted bipartite graph in which the nodes represent the clusters, the edges represent the non empty intersection between two clusters, and the weight of an edge is the number of common items. We introduce the so-called D-family-matching problem on intersection graphs, with D the upper-bound on the diameter of the graph induced by the clusters of any meta-cluster. First we prove NP-completeness and APX-hardness results, and unbounded approximation ratio of simple strategies. Second, we design exact polynomial time dynamic programming algorithms for some classes of graphs (in particular trees). Then, we prove spanning-tree based efficient algorithms for general graphs. Our experiments illustrate the role of D as a scale parameter providing information on the relationship between clusters within a clustering and in-between two clusterings. They also show the advantages of our built-in mapping over classical cluster comparison measures such as the variation of information (VI).