Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter at most two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the editing operations are vertex deletions). Answering an open question, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then, focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, outperforming a standard CPLEX solver in most instances of an established biological test data set.

Abstract Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal , if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration $$\varDelta $$ Δ , referred to as $$\varDelta $$ Δ - restless temporal paths . This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the “restless variant” of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the distance to disjoint path of the underlying graph, which implies W[1]-hardness for many other parameters like feedback vertex number and pathwidth. A natural question is thus whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number , which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.

Computing a (short) path between two vertices is one of the most fundamental primitives in graph algorithmics. In recent years, the study of paths in temporal graphs, that is, graphs where the vertex set is fixed but the edge set changes over time, gained more and more attention. A path is time-respecting, or temporal, if it uses edges with non-decreasing time stamps. We investigate a basic constraint for temporal paths, where the time spent at each vertex must not exceed a given duration Δ, referred to as Δ-restless temporal paths. This constraint arises naturally in the modeling of real-world processes like packet routing in communication networks and infection transmission routes of diseases where recovery confers lasting resistance. While finding temporal paths without waiting time restrictions is known to be doable in polynomial time, we show that the "restless variant" of this problem becomes computationally hard even in very restrictive settings. For example, it is W[1]-hard when parameterized by the feedback vertex number or the pathwidth of the underlying graph. The main question thus is whether the problem becomes tractable in some natural settings. We explore several natural parameterizations, presenting FPT algorithms for three kinds of parameters: (1) output-related parameters (here, the maximum length of the path), (2) classical parameters applied to the underlying graph (e.g., feedback edge number), and (3) a new parameter called timed feedback vertex number, which captures finer-grained temporal features of the input temporal graph, and which may be of interest beyond this work.

Modern-day social 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 (people) are represented by time-stamped edges. One of the most fundamental problems in social network analysis is community detection and within community detection, 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 for listing static cliques to listing Δ-cliques. We continue this work and improve and extend this algorithm to list temporal k-plexes, a temporal version of k-plexes, which are one of many popular clique relaxations. We define a Δ-$k$-plex as a set of vertices with a lifetime, where during the lifetime each vertex has an edge to all but at most k–1 vertices at least once every Δ + 1 consecutive time steps. We develop an algorithm for listing all maximal Δ-$k$-plexes and perform experiments on real-world networks that demonstrate the practical feasibility of our approach. In particular, for the special case of listing Δ-1-plexes (Δ-cliques), we observe that our algorithm is significantly faster than the previous algorithm by Himmel et al

Dynamics of interactions play an increasingly important role in the analysis of complex networks. A modeling framework to capture this are temporal graphs. We focus on enumerating Δ-cliques, an extension of the concept of cliques to temporal graphs: for a given time period Δ, a Δ-clique in a temporal graph is a set of vertices and a time interval such that all vertices interact with each other at least after every Δ time steps within the time interval. Viard, Latapy, and Magnien [ASONAM 2015] proposed a greedy algorithm for enumerating all maximal Δ-cliques in temporal graphs. In contrast to this approach, we adapt to the temporal setting the Bron-Kerbosch algorithm - an efficient, recursive backtracking algorithm which enumerates all maximal cliques in static graphs. We obtain encouraging results both in theory (concerning worst-case time analysis based on the parameter “Δ-slice degeneracy” of the underlying graph) as well as in practice with experiments on real-world data. The latter culminates in a significant improvement for most interesting Δ-values concerning running time in comparison with the algorithm of Viard, Latapy, and Magnien (typically two orders of magnitude).