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

We study the problem of computing isocontours in static and dynamic road networks, where the objective is to identify the boundary of the region that is reachable from a given source within a certain amount of time (or another limited resource). Although there is a wide range of practical applications for this problem (e.g., urban planning, geomarketing, visualizing the cruising range of a vehicle), there has been little research on fast algorithms for large, realistic inputs, and existing approaches tend to compute more information than necessary. Our contribution is twofold: (1) We propose compact but sufficient definitions of isocontours, based on which, (2) we provide several easy-to-parallelize, scalable algorithmic approaches for faster computation. By extensive experimental analysis, we demonstrate that our techniques enable interactive isocontour computation within milliseconds even on continental networks, significantly faster than the state-of-the-art.

#### Scalable Kernelization for Maximum Independent Sets

Hespe, Demian; Schulz, Christian; Strash, DarrenWe 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.

The state-of-the-art tools for practical graph canonization are all based on the indivi\-dualization-refinement paradigm, and their difference is primarily in the choice of heuristics they include and in the actual tool implementation. It is thus not possible to make a direct comparison of how individual algorithmic ideas affect the performance on different graph classes. We present an algorithmic software framework that facilitates implementation of heuristics as independent extensions to a common core algorithm. It therefore becomes easy to perform a detailed comparison of the performance and behaviour of different algorithmic ideas. Implementations are provided of a range of algorithms for tree traversal, target cell selection, and node invariant, including choices from the literature and new variations. The framework readily supports extraction and visualization of detailed data from separate algorithm executions for subsequent analysis and development of new heuristics. Using collections of different graph classes we investigate the effect of varying the selections of heuristics, often revealing exactly which individual algorithmic choice is responsible for particularly good or bad performance. On several benchmark collections, including a newly proposed class of difficult instances, we additionally find that our implementation performs better than the current state-of-the-art tools.

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