#### 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.

*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 introduce new and simple algorithms for the calculation of the number of perfect matchings of complex weighted, undirected graphs with and without loops. Our compact formulas for the hafnian and loop hafnian of $n \times n $ complex matrices run in $O(n^3 2^{n/2})$ time, are embarrassingly parallelizable and, to the best of our knowledge, are the fastest exact algorithms to compute these quantities. Despite our highly optimized algorithm, numerical benchmarks on the Titan supercomputer with matrices up to size $56 \times 56$ indicate that one would require the 288000 CPUs of this machine for about a month and a half to compute the hafnian of a $100 \times 100$ matrix.