We obtain hardness of approximation results for the \(\ell_p\)-Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer \(p \in [2,\infty)\), we show a hardness of \(\Omega\left( p(\log n / \log^2 \log n)^{1 - 1/p} \right)\) for both polynomial- and quasi-polynomial-time approximation algorithms. This nearly matches the approximation factor of \(O\left( p(\log n / \log \log n)^{1 - 1/p} \right)\) achieved by a quasi-polynomial-time algorithm of Makarychev, Ovsiankin, and Tani (ICALP 2025). No hardness of approximation results were previously known for any \(p \lt \infty\). We also present results for the case where \(p\) is a function of \(n\).

We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph \(G\), compute a vertex-cut \((L, S, R)\) in \(G\) of minimum value, which is defined to be the total weight of all vertices in \(S\). The problem, together with its edge-based variant, is one of the most basic in graph theory and algorithms, and has been studied extensively. The fastest currently known algorithm for directed global minimum vertex-cut (Henzinger, Rao and Gabow, FOCS 1996 and J. Algorithms 2000) has running time \(\tilde{O}(mn)\), where \(m\) and \(n\) denote the number of edges and vertices in the input graph, respectively. A long line of work over the past decades led to faster algorithms for other main versions of the problem, including the undirected edge-based setting (Karger, STOC 1996 and J. ACM 2000), directed edge-based setting (Cen et al., FOCS 2021), and undirected vertex-based setting (Chuzhoy and Trabelsi, STOC 2025). However, for the vertex-based version in directed graphs, the 29 year-old \(\tilde{O}(mn)\)-time algorithm of Henzinger, Rao and Gabow remains the state of the art to this day, in all edge-density regimes.

We develop new (1+є)-approximation algorithms for finding the global minimum edge-cut in a directed edge-weighted graph, and for finding the global minimum vertex-cut in a directed vertex-weighted graph. Our algorithms are randomized, and have a running time of O(m1+o(1)/є) on any m-edge n-vertex input graph, assuming all edge/vertex weights are polynomially-bounded. In particular, for any constant є>0, our algorithms have an almost-optimal running time of O(m1+o(1)). The fastest previously-known running time for this setting, due to (Cen et al., FOCS 2021), is O(min{n2/є2,m1+o(1)√n}) for Minimum Edge-Cut, and O(n2/є2) for Minimum Vertex-Cut.

In this paper, we study the individual preference (IP) stability, which is an notion capturing individual fairness and stability in clustering. Within this setting, a clustering is $\alpha$-IP stable when each data point’s average distance to its cluster is no more than $\alpha$ times its average distance to any other cluster. In this paper, we study the natural local search algorithm for IP stable clustering. Our analysis confirms a $O(\log n)$-IP stability guarantee for this algorithm, where $n$ denotes the number of points in the input. Furthermore, by refining the local search approach, we show it runs in an almost linear time, $\tilde{O}(nk)$.

Given a large edge-capacitated network G and a subset of k vertices called terminals, an (exact) flow sparsifier is a small network G' that preserves (exactly) all multicommodity flows that can be routed between the terminals. Flow sparsifiers were introduced by Leighton and Moitra [STOC 2010], and have been studied and used in many algorithmic contexts. A fundamental question that remained open for over a decade, asks whether every k-terminal network admits an exact flow sparsifier whose size is bounded by some function f (k) (regardless of the size of G or its capacities). We resolve this question in the negative by proving that there exist 6-terminal networks G whose flow sparsifiers G' must have arbitrarily large size. This unboundedness is perhaps surprising, since the analogous sparsification that preserves all terminal cuts (called exact cut sparsifier or mimicking network) admits sparsifiers of size fo(k) ≤ 22k [Hagerup, Katajainen, Nishimura, and Ragde, JCSS 1998]. We prove our results by analyzing the set of all feasible demands in the network, known as the demand polytope. We identify an invariant of this polytope, essentially the slope of certain facets, that can be made arbitrarily large even for k = 6, and implies an explicit lower bound on the size of the network. We further use this technique to answer, again in the negative, an open question of Seymour [JCTB 2015] regarding flow-sparsification that uses only contractions and preserves the infeasibility of one demand vector. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.07363 † The first version of this paper proved a weaker statement of Theorem 1.2 with 4 commodities. The current statement has only 3 commodities, and now fully refutes Seymour's conjectures. In addition, the current version describes implications to the 0-extension problem, see Section 1.4.