A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k²g) triangles, which is optimal. This is an improvement over the previous best bound k^O(k) g² of Gao, Richter and Seymour [Journal of Combinatorial Theory, Series B, 1996].

Deformations of knots and links in ambient space can be studied combinatorially on their diagrams via local modifications called Reidemeister moves. While it is well-known that, in order to move between equivalent diagrams with Reidemeister moves, one sometimes needs to insert excess crossings, there are significant gaps between the best known lower and upper bounds on the required number of these added crossings. In this article, we study the problem of turning a diagram of a split link into a split diagram, and we show that there exist split links with diagrams requiring an arbitrarily large number of such additional crossings. More precisely, we provide a family of diagrams of split links, so that any sequence of Reidemeister moves transforming a diagram with c crossings into a split diagram requires going through a diagram with Ω(√c) extra crossings. Our proof relies on the framework of bubble tangles, as introduced by the first two authors, and a technique of Chambers and Liokumovitch to turn homotopies into isotopies in the context of Riemannian geometry.

Abstract. Given [Formula: see text] recording pairwise distances, the Metric Violation Distance problem asks to compute the [Formula: see text] distance between [Formula: see text] and the metric cone; i.e., modify the minimum number of entries of [Formula: see text] to make it a metric. Due to its large number of applications in various data analysis and optimization tasks, this problem has been actively studied recently. We present an [Formula: see text]-approximation algorithm for Metric Violation Distance, exponentially improving the previous best approximation ratio of [Formula: see text] of Fan, Raichel, and Van Buskirk [ SODA, 2018]. Furthermore, a major strength of our algorithm is its simplicity and running time. We also study the related problem of Ultrametric Violation Distance, where the goal is to compute the [Formula: see text] distance to the cone of ultrametrics, and achieve a constant factor approximation algorithm. The Ultrametric Violation Distance problem can be regarded as an extension of the problem of fitting ultrametrics studied by Ailon and Charikar [ SIAM J. Comput., 2011] and by Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [ FOCS, 2021] from [Formula: see text] norm to [Formula: see text] norm. We show that this problem can be favorably interpreted as an instance of Correlation Clustering with an additional hierarchical structure, which we solve using a new [Formula: see text]-approximation algorithm for correlation clustering that has the structural property that it outputs a refinement of the optimum clusters. An algorithm satisfying such a property can be considered of independent interest. We also provide an [Formula: see text]-approximation algorithm for a weighted version of Ultrametric Violation Distance. Finally, we investigate the complementary version of these problems where one aims at choosing a maximum number of entries of [Formula: see text] forming an (ultra)metric. In stark contrast to the minimization versions, we prove that these maximization versions are hard to approximate within any constant factor assuming the Unique Games Conjecture.

While the problem of computing the genus of a knot is now fairly well understood, no algorithm is known for its four-dimensional variants, both in the smooth and in the topological locally flat category. In this article, we investigate a class of knots and links called Hopf arborescent links, which are obtained as the boundaries of some iterated plumbings of Hopf bands. We show that for such links, computing the genus defects, which measure how much the four-dimensional genera differ from the classical genus, is decidable. Our proof is non-constructive, and is obtained by proving that Seifert surfaces of Hopf arborescent links under a relation of minors defined by containment of their Seifert surfaces form a well-quasi-order.

We consider the ℓ0-Low Rank Approximation problem, where the input consists of a matrix A ∈ ℝnR×nc and an integer k, and the goal is to find a matrix B of rank at most k that minimizes ‖A — B‖0, which is the number of entries where A and B differ. For any constant k and ɛ > 0, we present a polynomial time (1 + ɛ)- approximation time for this problem, which significantly improves the previous best poly(k)-approximation.

In this article, we investigate short topological decompositions of non-orientable surfaces and provide algorithms to compute them. Our main result is a polynomial-time algorithm that for any graph embedded on a non-orientable surface computes a canonical non-orientable system of loops so that any loop from the canonical system intersects any edge of the graph in at most 30 points. The existence of such short canonical systems of loops was well known in the orientable case and an open problem in the non-orientable case. Our proof techniques combine recent work of Schaefer-Štefankovič with ideas coming from computational biology, specifically from the signed reversal distance algorithm of Hannenhalli-Pevzner. The existence of short canonical non-orientable systems of loops confirms a special case of a conjecture of Negami on the joint crossing number of two embeddable graphs. We also provide a correction for an argument of Negami bounding the joint crossing number of two non-orientable graph embeddings. Finally, we provide a generalization of O ( g )-universal shortest path metrics to non-orientable surfaces.

International audience

A closed quasigeodesic on a convex polyhedron is a closed curve that is locally straight outside of the vertices, where it forms an angle at most $π$ on both sides. While the existence of a simple closed quasigeodesic on a convex polyhedron has been proved by Pogorelov in 1949, finding a polynomial-time algorithm to compute such a simple closed quasigeodesic has been repeatedly posed as an open problem. Our first contribution is to propose an extended definition of quasigeodesics in the intrinsic setting of (not necessarily convex) polyhedral spheres, and to prove the existence of a weakly simple closed quasigeodesic in such a setting. Our proof does not proceed via an approximation by smooth surfaces, but relies on an adapation of the disk flow of Hass and Scott to the context of polyhedral surfaces. Our second result is to leverage this existence theorem to provide a finite algorithm to compute a weakly simple closed quasigeodesic on a polyhedral sphere. On a convex polyhedron, our algorithm computes a simple closed quasigeodesic, solving an open problem of Demaine, Hersterberg and Ku.

Given $x\in(\mathbb{R}_{\geqslant 0})(_{2}^{[n]})$ recording pairwise distances, the Metric Violation Distance problem asks to compute the $\ell_{0}$ distance between x and the metric cone; i.e., modify the minimum number of entries of x to make it a metric. Due to its large number of applications in various data analysis and optimization tasks, this problem has been actively studied recently. We present an $O(\log n)$-approximation algorithm for METRIC VIOLATION Distance, exponentially improving the previous best approximation ratio of $O(OPT^{1/3})$ of Fan, Raichel, and Van Buskirk [SODA, 2018]. Furthermore, a major strength of our algorithm is its simplicity and running time. We also study the related problem of Ultrametric Violation Distance, where the goal is to compute the $\ell_{0}$ distance to the cone of ultrametrics, and achieve a constant factor approximation algorithm. The ULTRAMETRIC VIOLATION DISTANCE problem can be regarded as an extension of the problem of fitting ultrametrics studied by Ailon and Charikar [SIAM J. Computing, 2011] and by Cohen-Addad, Das, Kipouridis, Parotsidis, and Thorup [FOCS, 2021] from $\ell_{1}$ norm to $\ell_{0}$ norm. We show that this problem can be favorably interpreted as an instance of CORRELATION CLUSTERING with an additional hierarchical structure, which we solve using a new $O(1)$-approximation algorithm for correlation clustering that has the structural property that it outputs a refinement of the optimum clusters. An algorithm satisfying such a property can be considered of independent interest. We also provide an $O(\log n\log\log n)$ approximation algorithm for weighted instances. Finally, we investigate the complementary version of these problems where one aims at choosing a maximum number of entries of x forming an (ultra-)metric. In stark contrast with the minimization versions, we prove that these maximization versions are hard to approximate within any constant factor assuming the Unique Games Conjecture.

We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of De Graaf and Schrijver [ J. Comb. Theory Ser. B , 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound, we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms—the cluster and pipe expansions—to the study of curves on surfaces. As corollaries, we present two efficient algorithms for curves and graphs on surfaces. First, we provide a polynomial-time algorithm to convert any given multicurve on a surface into minimal position. Such an algorithm only existed for single closed curves, and it is known that previous techniques do not generalize to the multicurve case. Second, we provide a polynomial-time algorithm to reduce any k -terminal plane graph (and more generally, surface graph) using degree-1 reductions, series-parallel reductions, and Δ Y -transformations for arbitrary integer k . Previous algorithms only existed in the planar setting when k ≤ 4, and all of them rely on extensive case-by-case analysis based on different values of k . Our algorithm makes use of the connection between electrical transformations and homotopy moves and thus solves the problem in a unified fashion.

In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the complexity of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve γ, and a collection of disjoint normal curves Δ, there is a polynomial-time algorithm to decide if γ lies in the normal subgroup generated by components of Δ in the fundamental group of the surface after attaching the curves to a basepoint.

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus G has a cut graph of length at most a given value. We prove a time lower bound for this problem of n Ω( g log g ) conditionally to the ETH. In other words, the first n O(g) -time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year-old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals , is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n Ω( gt + g 2 + t log ( g + t )) , conditionally to the ETH, for any choice of the genus g ≥ 0 of the graph and the number of terminals t ≥ 4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a gridlike structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value G of the genus.

For an undirected edge-weighted graph $G$ and a set $R$ of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from $G$ disconnects each pair in $R$. We provide an algorithm computing a $(1+\varepsilon)$-approximation of the minimum multicut of a graph $G$ in time $(g+t)^{(O(g+t)^3)}\cdot(1/\varepsilon)^{O(g+t)} \cdot n \log n$, where $g$ is the genus of $G$ and $t$ is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when $g=0$). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces. Interestingly, such topological techniques seem necessary even for the planar case. We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight toward our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which $G$ is embedded.

We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time during the process. The best known upper bound before was exponential, which can be obtained by combining the algorithm of de Graaf and Schrijver [J. Comb. Theory Ser. B, 1997] together with an exponential upper bound on the number of possible surface maps. To obtain the new upper bound we apply tools from hyperbolic geometry, as well as operations in graph drawing algorithms—the cluster and pipe expansions—to the study of curves on surfaces. As corollaries, we present two efficient algorithms for curves and graphs on surfaces. First, we provide a polynomial-time algorithm to convert any given multicurve on a surface into minimal position. Such an algorithm only existed for single closed curves, and it is known that previous techniques do not generalize to the multicurve case. Second, we provide a polynomial-time algorithm to reduce any k-terminal plane graph (and more generally, surface graph) using degree-1 reductions, series-parallel reductions, and ΔY-transformations for arbitrary integer k. Previous algorithms only existed in the planar setting when k ≤ 4, and all of them rely on extensive case-by-case analysis based on different values of k. Our algorithm makes use of the connection between electrical transformations and homotopy moves, and thus solves the problem in a unified fashion.

International audience

We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cut graph of a graph G embedded on a surface S is a subgraph of G whose removal from S leaves a disk. We consider the problem of deciding whether an unweighted graph embedded on a surface of genus g has a cut graph of length at most a given value. We prove a time lower bound for this problem of n^{Omega(g/log g)} conditionally to ETH. In other words, the first n^{O(g)}-time algorithm by Erickson and Har-Peled [SoCG 2002, Discr. Comput. Geom. 2004] is essentially optimal. We also prove that the problem is W[1]-hard when parameterized by the genus, answering a 17-year old question of these authors. A multiway cut of an undirected graph G with t distinguished vertices, called terminals, is a set of edges whose removal disconnects all pairs of terminals. We consider the problem of deciding whether an unweighted graph G has a multiway cut of weight at most a given value. We prove a time lower bound for this problem of n^{Omega(sqrt{gt + g^2}/log(gt))}, conditionally to ETH, for any choice of the genus g >=0 of the graph and the number of terminals t >=4. In other words, the algorithm by the second author [Algorithmica 2017] (for the more general multicut problem) is essentially optimal; this extends the lower bound by the third author [ICALP 2012] (for the planar case). Reductions to planar problems usually involve a grid-like structure. The main novel idea for our results is to understand what structures instead of grids are needed if we want to exploit optimally a certain value g of the genus.

In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves γ1 and γ2 on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between γ1 and γ2 where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Fréchet Distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.

We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O(n2) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O(n4) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

In this paper, we give a conditional lower bound of nΩ(k) on running time for the classic k-median and k-means clustering objectives (where n is the size of the input), even in low-dimensional Euclidean space of dimension four, assuming the Exponential Time Hypothesis (ETH). We also consider k-median (and k-means) with penalties where each point need not be assigned to a center, in which case it must pay a penalty, and extend our lower bound to at least three-dimensional Euclidean space. This stands in stark contrast to many other geometric problems such as the traveling salesman problem, or computing an independent set of unit spheres. While these problems benefit from the so-called (limited) blessing of dimensionality, as they can be solved in time nO(k1-1/d) or 2n1-1/d in d dimensions, our work shows that widely-used clustering objectives have a lower bound of nΩ(k), even in dimension four. We complete the picture by considering the two-dimensional case: we show that there is no algorithm that solves the penalized version in time less than , and provide a matching upper bound of . The main tool we use to establish these lower bounds is the placement of points on the moment curve, which takes its inspiration from constructions of point sets yielding Delaunay complexes of high complexity.

For an undirected edge-weighted graph G and a set R of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from G disconnects each pair in R. We provide an algorithm computing a (1 + ε)-approximation of the minimum multicut of a graph G in time (g + t)(O(g+t)3) · (1/ε)°(g+t) · n log n, where g is the genus of G and t is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when g = 0). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces (even in the planar case). We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight towards our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which G is embedded.

We prove that the problem of deciding whether a 2- or 3-dimensional simplicial complex embeds into ℝ3 is NP-hard. This stands in contrast with the lower dimensional cases which can be solved in linear time, and a variety of computational problems in ℝ3 like unknot or 3-sphere recognition which are in NP ∩ co-NP (assuming the generalized Riemann hypothesis). Our reduction encodes a satisfiability instance into the embeddability problem of a 3-manifold with boundary tori, and relies extensively on techniques from low-dimensional topology, most importantly Dehn fillings on link complements.

We investigate the complexity of finding an embedded non-orientable surface of Euler genus g in a triangulated 3-manifold. This problem occurs both as a natural question in low-dimensional topology, and as a first non-trivial instance of embeddability of complexes into 3-manifolds. We prove that the problem is NP-hard, thus adding to the relatively few hardness results that are currently known in 3-manifold topology. In addition, we show that the problem lies in NP when the Euler genus g is odd, and we give an explicit algorithm in this case.

The classical theorem of Fáry states that every planar graph can be represented by an embedding in which every edge is represented by a straight line segment. We consider generalizations of Fáry’s theorem to surfaces equipped with Riemannian metrics. In this setting, we require that every edge is drawn as a shortest path between its two endpoints and we call an embedding with this property a shortest path embedding . The main question addressed in this paper is whether given a closed surface S , there exists a Riemannian metric for which every topologically embeddable graph admits a shortest path embedding. This question is also motivated by various problems regarding crossing numbers on surfaces. We observe that the round metrics on the sphere and the projective plane have this property. We provide flat metrics on the torus and the Klein bottle which also have this property. Then we show that for the unit square flat metric on the Klein bottle there exists a graph without shortest path embeddings. We show, moreover, that for large g , there exist graphs G embeddable into the orientable surface of genus g , such that with large probability a random hyperbolic metric does not admit a shortest path embedding of G , where the probability measure is proportional to the Weil–Petersson volume on moduli space. Finally, we construct a hyperbolic metric on every orientable surface S of genus g , such that every graph embeddable into S can be embedded so that every edge is a concatenation of at most O ( g ) shortest paths.

How much cutting is needed to simplify the topology of a surface? We provide bounds for several instances of this question, for the minimum length of topologically non-trivial closed curves, pants decompositions, and cut graphs with a given combinatorial map in triangulated combinatorial surfaces (or their dual cross-metric counterpart).

We investigate the following problem: Given two embeddings G1 and G2 of the same abstract graph G on an orientable surface S, decide whether G1 and G2 are isotopic; in other words, whether there exists a continuous family of embeddings between G1 and G2. We provide efficient algorithms to solve this problem in two models. In the first model, the input consists of the arrangement of G1 (resp., G2) with a fixed graph cellularly embedded on S; our algorithm is linear in the input complexity, and thus, optimal. In the second model, G1 and G2 are piecewise-linear embeddings in the plane minus a finite set of points; our algorithm runs in O(n3/2log n) time, where n is the complexity of the input.

We that every n-point tree metric admits a (1 + ε)-embedding into ℓ1C(ε)log n, for every ε > 0, where C(ε) ≤ . This matches the natural volume lower bound up to a factor depending only on ε. Previously it was unknown whether even complete binary trees on n nodes could be embedded in ℓ1O(log n) with O(1) distortion. For complete d-ary trees, our construction achieves .