Evangelos Kipouridis

SODA Conference 2025 Conference Paper

Clustering to Minimize Cluster-Aware Norm Objectives

• Martin G. Herold
• Evangelos Kipouridis
• Joachim Spoerhase

ICML Conference 2025 Conference Paper

Towards Better-than-2 Approximation for Constrained Correlation Clustering

• Andreas Kalavas
• Evangelos Kipouridis
• Nithin Varma 0001

In the Correlation Clustering problem, we are given an undirected graph and are tasked with computing a clustering (partition of the nodes) that minimizes the sum of the number of edges across different clusters and the number of non-edges within clusters. In the constrained version of this problem, the goal is to compute a clustering that satisfies additional hard constraints mandating certain pairs to be in the same cluster and certain pairs to be in different clusters. Constrained Correlation Clustering is APX-Hard, and the best known approximation factor is 3 (van Zuylen et al. [SODA ’07]). In this work, we show that in order to obtain a better-than-2 approximation, solving the (exponentially large) Constrained Cluster LP would be sufficient. [The peer-reviewed version of this article claimed an efficient algorithm for solving the Constrained Cluster LP. An error in the proof, that the authors discovered after the review process, led them to revise the results to be conditional on the existence of a valid LP solution. ]

SODA Conference 2024 Conference Paper

Dynamic Dynamic Time Warping

• Karl Bringmann
• Nick Fischer
• Ivor van der Hoog
• Evangelos Kipouridis
• Tomasz Kociumaka
• Eva Rotenberg

SODA Conference 2023 Conference Paper

Faster Computation of 3-Edge-Connected Components in Digraphs

• Loukas Georgiadis
• Evangelos Kipouridis
• Charis Papadopoulos
• Nikos Parotsidis

We present an Õ ( m 3/2 ) time randomized (Monte Carlo) algorithm for computing the 3-edge-connected components of a digraph with m edges and n vertices. This constitutes the first improvement since the algorithm of Nagamochi & Watanabe from 1993, which runs in O(m · n ) time. Thus, our algorithm is the first that overcomes the run-time of O ( n ) computations of 3-bounded max-flows (that is, computations of the value min{Flow( s, t ), 3} for O ( n ) pairs s-t ). Our algorithm involves a combination of known and new techniques together with new structural insights on the interactions between directed min-cuts. One novel aspect that we introduce is an efficient graph operation G <s> for replacing a set of vertices S that is disconnected from V\S by an edge-cut of size 2 (2-out set), with a gadget of small size that preserves the pairwise connectivity among the vertices of V\S. Another main ingredient of our approach is an extension of the framework for computing the vertex-connectivity (or edge-connectivity) in a digraph [Nanongkai et al. , STOC'19]. This extension allows us to efficiently identify either all small 2-out sets of vertices, or identify enough 2-out sets whose total internal volume is a constant fraction of the edges of the graph. Repeatedly replacing each identified 2-out set S with a small gadget (using the G <s> and G < V\S > operations) either shrinks the size of the graph by a constant fraction, or concludes that no small 2-out set exists. We believe that our techniques may be of independent interest. Finally, we augment our algorithm with a data structure that can report in constant time the edges of some edge-cut of size at most 2 that disconnects any two query vertices u, v, or report in constant time that no such edge-cut exists.

TCS Journal 2023 Journal Article

Threshold-based network structural dynamics

• Evangelos Kipouridis
• Paul G. Spirakis
• Kostas Tsichlas

The interest in dynamic processes on networks is steadily rising in recent years. In this paper, we consider the ( α, β ) -Threshold Network Dynamics ( ( α, β ) -Dynamics), where α ≤ β, in which only structural dynamics (edge dynamics of the network) are allowed, guided by local threshold rules executed by each node. In particular, in each discrete round t, each active pair of nodes u and v, computes a value E ( u, v ) (the potential of the pair) as a function of the local structure of the network at round t around the two nodes. If E ( u, v ) < α then the link (if it exists) between u and v is removed; if α ≤ E ( u, v ) < β then an existing link among u and v is maintained; if β ≤ E ( u, v ) then a link between u and v is established if not already present. New nodes cannot be inserted as a result of the protocol, and existing nodes cannot be removed. The microscopic structure of ( α, β ) -Dynamics appears to be simple, so that we are able to rigorously argue about it, but still flexible, so that we are able to design meaningful microscopic local rules that give rise to interesting macroscopic behaviors. Our goals are the following: a) to investigate the properties of the ( α, β ) -Threshold Network Dynamics and b) to show that ( α, β ) -Dynamics is expressive enough to solve complex problems on networks. Our contribution in these directions is twofold. We rigorously exhibit the claim about the expressiveness of ( α, β ) -Dynamics, both by designing a simple protocol that provably computes the k-core of the network as well as by showing that ( α, β ) -Dynamics are in fact Turing-Complete. Second and most important, we construct general tools for proving stabilization that work for a subclass of ( α, β ) -Dynamics and prove speed of convergence in a restricted setting.

FOCS Conference 2021 Conference Paper

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

• Vincent Cohen-Addad
• Debarati Das 0001
• Evangelos Kipouridis
• Nikos Parotsidis
• Mikkel Thorup

We consider the numerical taxonomy problem of fitting a positive distance function $\mathcal{D}: \binom{S}{2}\rightarrow \mathbb{R}_{> 0}$ by a tree metric. We want a tree $T$ with positive edge weights and including $S$ among the vertices so that their distances in $T$ match those in $\mathcal{D}$. A nice application is in evolutionary biology where the tree $T$ aims to approximate the branching process leading to the observed distances in $\mathcal{D}$ [Cavalli-Sforza and Edwards 1967]. We consider the total error, that is the sum of distance errors over all pairs of points. We present a deterministic polynomial time algorithm minimizing the total error within a constant factor. We can do this both for general trees, and for the special case of ultrametrics with a root having the same distance to all vertices in $S$. The problems are APX-hard, so a constant factor is the best we can hope for in polynomial time. The best previous approximation factor was $O((\log n)(\log\log n)$ ) by Ailon and Charikar [2005] who wrote “Determining whether an $O(1)$ approximation can be obtained is a fascinating question”.