CS Paper Radar

Metric Planarity Testing is Hard

Anubhav Dhar, Debajyoti Kar, Sándor Kisfaludi-Bak, Hung Le, Bartłomiej Lewandowski, Karol Węgrzycki

cs.DS ·submitted 2026-10-11 15:06 UTC · v1
theory

Abstract

A key milestone in algorithmic graph theory is Hopcroft and Tarjan's 1974 linear-time algorithm for graph planarity testing. At a workshop in 2002, Linial and Rabinovich asked for either a polynomial-time algorithm or an NP-hardness proof for metric planarity testing: given a metric space $(X,d_X)$, determine whether there exists an edge-weighted planar graph $G=(V,E,w)$ with $X\subseteq V$ that realizes the distances in $X$, meaning that $d_G(x,y)=d_X(x,y)$ for every $x,y\in X$. This question arose in the context of research on metric embeddings and their applications in computer science since the mid-1990s. Over the past few decades, polynomial-time algorithms have been developed for several special cases. In this work, we show that metric planarity testing is NP-hard, in sharp contrast to graph planarity testing. Our reduction yields a stronger result: under the Exponential Time Hypothesis (ETH), no $2^{o(n)}$-time algorithm for metric planarity testing exists, where $n$ is the number of points in the metric. To complement our ETH lower bound, we give two algorithmic results: (i) an algorithm for computing a metric planar embedding in $2^{\tilde{O}(n^2)}$ time and (ii) a $(1+ε)$-approximation algorithm in $2^{\tilde{O}(n)}$ time for any fixed $ε\in(0,1)$. The second algorithm produces a planar graph that preserves the input metric up to a factor of $(1+ε)$.

Comment
9 figures, 27 pages

Closest papers

Nearest neighbours by meaning across the whole index.

How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics

cs.DS ·2026-10-06 ·Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Saket Saurabh, Chinmay Sonar +2 more
hot direction similarity 0.66
Abstract

Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most $k$ weights can be changed to form a metric. Motivated by metric repair for noisy data, the problem admits a polynomial-time $O(\log n)$-approximation due to Cohen-Addad, Fan, Lee and de Mesmay [SIAM J. Comput., 2025]. In the context of parameterized complexity, Fan, Gilbert, Raichel, Sonthalia and Van Buskirk [SWAT 2020] gave a $k^{O(k)}n^{O(1)}$-time algorithm. Fomin, Golovach and More [IPEC 2026] obtained an $O(k^2)$ kernel and a single-exponential algorithm for the ultrametric case. They asked whether general metrics admit a single-exponential algorithm and a polynomial kernel, and whether the tree-metric analogue is fixed-parameter tractable. We answer all three questions. We give a $2^{O(k)}n^{O(1)}$-time algorithm and prove that, unless ETH fails, no $2^{o(k)}n^{O(1)}$-time algorithm exists, even when all input distances lie in $\{1,2,3\}$. We also give a kernel with at most $6k$ vertices. The kernel supports solution lifting and can precede any approximation algorithm. Combined with the $O(\log n)$-approximation of Cohen-Addad, Fan, Lee and de Mesmay, it yields an $O(\log \mathrm{OPT})$-approximation at no asymptotic cost in running time. Both results extend to an interval generalization in which each edge $e$ has an observed value $M_e$ and an admissible range $[A_e,B_e]$ within which it may be reassigned; the kernel then has $7k$ vertices. Finally, Tree Metric Violation Distance is fixed-parameter tractable and solvable in $k^{O(k)}n^{O(1)}$ time.

0.49

Metric Dimension is NP-complete on Graphs of Treewidth Two

cs.CC cs.DM ·2026-10-15 ·Tristan Benoit
similarity 0.66
Abstract · v3: NP-completeness extended to two-connected two-terminal series-parallel graphs of pathwidth at most five; v2: open questions corrected. 8…

The metric dimension of a connected graph is the least number of vertices whose distance vectors distinguish all vertices. We show that deciding whether the metric dimension of a graph is at most a given integer is NP-complete on graphs of treewidth at most two, and even on two-connected two-terminal series-parallel graphs of pathwidth at most five. As the problem is polynomial on trees, the graphs of treewidth one, this settles the treewidth threshold of its hardness, which was known to lie between two and twenty-four. The reduction is from satisfiability of formulas in which every literal occurs at most twice. To such a formula with $n$ clauses and $r$ variables it associates a two-terminal series-parallel graph $G_\varphi$ with $O((n+r)^2)$ vertices and pathwidth at most five, whose metric dimension is $2(n+r)+7$ if the formula is satisfiable and $2(n+r)+8$ otherwise.

0.53

Improved Approximation and Hardness Results for the Monitoring Edge-Geodetic Set Problem

cs.DS ·2026-10-20 ·Davide Bilò, Giordano Colli, Stefano Leucci
theory similarity 0.66
Abstract · 18 pages, 4 figures

We study the \emph{Monitoring Edge-Geodetic Set} problem (MEG-Set), which asks for a minimum-cardinality set $M$ of vertices of an undirected graph $G$ of $n$ vertices such that every edge of $G$ belongs to all shortest paths between some pair of vertices in $M$. We present new approximation and hardness results for MEG-Set. On the positive side, we design a deterministic polynomial-time $O(n^{1/3}\log^{2/3}n)$-approximation algorithm, improving upon the previously best-known $O(\sqrt{n\log n})$ approximation ratio. On the negative side, for every constant $\varepsilon \in (0,1)$, we prove that the problem admits no polynomial-time $\big(2^{\log^{1-\varepsilon} n}\big)$-approximation algorithm, unless $\mathsf{NP}\subseteq \mathsf{DTIME}(n^{\operatorname{polylog} n})$. This substantially improves upon the previously known logarithmic inapproximability bound. We also prove that \megset is $\mathsf{NP}$-hard on planar $2$-degenerate graphs, whereas $\mathsf{NP}$-hardness was previously known for $1$-apex $2$-degenerate graphs. We conclude by observing a connection between monitoring edge-geodetic sets and subsetwise distance preservers, i.e., subgraphs that preserve distances between all pairs of vertices in $S\subseteq V(G)$. Specifically, we show that any upper bound on the size of the latter yields a lower bound on the size of the former.

0.23

Testing Implies Distance Estimation with Polynomial Loss

cs.DS math.CO ·2026-11-03 ·Gaia Carenini, Cameron Seth
similarity 0.66
Abstract

A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.

0.27

Complexity, approximation, and extension of proper $\{a,b\}$-edge-weightings

cs.DM cs.CCmath.CO ·2026-09-25 ·Péter Madarasi, Máté Simon
theory similarity 0.65
Abstract

For distinct integers $a$ and $b$, an $\{a,b\}$-edge-weighting assigns $a$ or $b$ to each edge and labels each vertex by the sum of its incident weights. Such a weighting is proper if adjacent vertices receive distinct labels. We prove that, for every fixed pair of distinct integers, deciding whether a proper weighting exists is NP-complete even for simple cubic planar graphs. On planar multigraphs with $m$ edges, we give an exact $2^{O(\sqrt m)}$-time algorithm and, assuming the Exponential Time Hypothesis (ETH), exclude $2^{o(\sqrt m)}$-time algorithms even for simple cubic planar graphs. As a consequence, locally irregular $2$-edge-coloring is NP-complete on simple cubic planar graphs, admits a deterministic $2^{O(\sqrt n)}$-time algorithm on $n$-vertex graphs in this class, and admits no $2^{o(\sqrt n)}$-time algorithm under ETH. For maximizing the number of edges joining vertices with distinct labels, we give a deterministic efficient polynomial-time approximation scheme (EPTAS) on planar multigraphs, a polynomial-time $1/2$-approximation on multigraphs, and APX-completeness even on simple cubic graphs. Extending a partial $\{a,b\}$-edge-weighting to a proper one is NP-complete for every fixed pair even on simple cubic planar bipartite graphs, while it is polynomial-time solvable on trees. The hardness persists even when the prescribed edges form disjoint paths of length $6$ and all edges of each path have the same prescribed weight.

0.23

Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein

cs.DM cs.CCmath.CO ·2026-10-12 ·Jens Breitung, Timo Gervens, Julius Pörzgen
similarity 0.65
Abstract

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

0.52

Search and Verification for Strategyproof Facility Location on Metric Graphs

cs.GT econ.TH ·2026-11-03 ·Krzysztof Rogowski, Marcin Dziubiński
theory similarity 0.64
Abstract · 57 pages, 1 figure. Submitted to STOC 2027

We study automated design of strategyproof (SP) mechanisms for randomized facility location on continuous metric graphs, with the objective of minimizing total distance. We develop methods for computing upper and lower bounds on the optimal approximation ratio achievable by SP mechanisms for a given graph and number of agents. For the lower bound, we propose a cost-preserving reduction to a finite domain that yields lower bounds for unrestricted SP mechanisms through linear programming dual certificates. For the upper bound, we introduce finite representations of mechanisms, called piecewise-linear attributions (PL attributions), that mix piecewise-linear deterministic mechanisms using affine weights on a triangulation of the report space. We show that for mechanisms represented by PL attributions, checking SP and an approximation guarantee reduces to finitely many quadratic nonnegativity tests over compact polytopes. With exact arithmetic and comparisons, each verification certifies the proposed property or returns locations where it fails. In addition, we introduce a strengthening of the incentive notion called strong strategyproofness. We show that for fixed component mechanisms and regions of a PL attribution, the strong strategyproofness requirement can be expressed by a finite number of linear constraints on the attribution coefficients. Using these theoretical results, we propose a heuristic procedure for computing an upper bound on the approximation ratio. We compute certified upper and lower bounds on several metric graphs and numerically evaluate the proposed search procedure. Lastly, we show that deterministic SP onto mechanisms on graphs are strongly strategyproof and admit PL attributions. Thus restricting attention to strongly strategyproof mechanisms admitting PL attributions loses no deterministic SP onto mechanisms.

0.20

Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth

cs.CC ·2026-11-06 ·Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz
theory similarity 0.64
Abstract

The metric dimension of a graph is the minimum size of a set of vertices whose distance vectors distinguish all vertices of the graph. We prove that \MetricDimension{} is NP-complete on planar graphs of treewidth and bag-connected treewidth exactly three. The graphs in our construction have no induced cycle longer than four and have (prefix-connected) pathwidth at most four. In particular, the problem admits no XP algorithm parameterized by bag-connected treewidth unless $\mathrm P=\mathrm{NP}$. This answers questions of Bonnet and Purohit and of Bousquet, Deschamps, and Parreau. We prove that the problem is fixed-parameter tractable when parameterized by bag-connected pathwidth.

0.17