NP-completeness of the ℓ 1 \ell_{1} -embedding problem for simple graphs as sphere-of-influence graphs

Stanislav Jabuka · 2025

Read NP-completeness of the ℓ 1 \ell_{1} -embedding problem for simple graphs as sphere-of-influence graphs by Stanislav Jabuka (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20740.txt.

Introduction

Stanislav Jabuka settles the complexity of a geometric representation question. Sphere-of-influence graphs arise by drawing balls around points and connecting overlapping ones. For the infinity metric, every simple graph arises this way; for every finite positive exponent, some graph fails. The borderline case of the l1 metric stayed open.

Jabuka proves the embeddability question there is promise NP-complete. Deciding whether a given simple graph is a sphere-of-influence graph in some Euclidean space under the l1 metric is computationally hard in the formal sense. NP-completeness does not answer whether all graphs embed, but it explains why the question resisted attack. A decision problem this hard is unlikely to yield a simple characterization, which redirects future work on the l1 case.

Catalog record

CREATORStanislav Jabuka
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE13 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-20740

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

NP-completeness of the ℓ 1 \ell_{1} -embedding problem for simple graphs as sphere-of-influence graphs Stanislav Jabuka Abstract . In graph theory an interesting question is whether for a fixed choice of p ∈ [ 0 , ∞ ] p\in[0,\infty] , all simple graphs appear as sphere-of-influence graphs in some Euclidean space with respect to the ℓ p \ell_{p} metric. The answer is affirmative for p = ∞ p=\infty , negative for any p ∈ ( 0 , ∞ ) p\in(0,\infty) , and unknown for p = 1 p=1 . The result of this work shows that for the case of p = 1 p=1 , this embeddability question is a (Promise) NP-Complete problem. 2020 Mathematics Subject Classification 05C12, 68R10, 68R12 1. Introduction 1.1. Background Let (M,d) be a metric space and X=\{X_{1},\dots,X_{n}\}\subset M be a finite subset. The radius of influence r_{i} of X_{i} is r_{i}=\min_{j\neq i}d(X_{i},X_{j}) , and the sphere of influence of X_{i} is S_{i}=\{x\in M\,|\,d(X_{i},x)<r_{i}\} . The sphere-of-influence graph , or SIG for short, of the subset X\subset M and induced by the metric d , is the graph with vertices X_{1},\dots,X_{n} , two of which share an edge if and only if d(X_{i},X_{j})<r_{i}+r_{j} (or equivalently, if their spheres of influence overlap). A central question in the theory of SIGs is whether any simple graph G is isometric to a SIG in (\mathbb{R}^{m},d_{p}) with the dimension m\geq 1 arbitrary, and with d_{p} being the \ell_{p} -metric d_{p}(x,y)=\left\{\begin{array}[]{cl}\left(|x_{1}-y_{1}|^{p}+\dots+|x_{n}-y_{n}|^{p}\right)^{1/p}&\quad;\quad p\in[1,\infty),\cr\max\{|x_{1}-y_{1}|,\dots,|x_{n}-y_{n}|\}&\quad;\quad p=\infty.\end{array}\right. The answer is ‘yes’ if p=\infty [ 5 , 14 ] , it is ‘no’ if p\in(1,\infty) [ 12 ] and is unknown if p=1 . We show that the case of p=1 leads to a (Promise) NP-Complete problem, lending credence to the difficulty of the problem. 1.2. \ell_{1} -embeddability and the cut cone CUT_{n} Consider a finite metric space (V_{n},d) with V_{n}=\{1,\dots,n\} . A cut of V_{n} is a subset C\subset V_{n} , which we view as “cutting” V_{n} into the disjoint pieces V_{n}=C\cup(V_{n}-C) . A cut creates a notion of distance on V_{n} , with two elements that lie in the same subset induced by the cut, either C or V_{n}-C , being distance 0 apart, and with two elements lying in opposite components of the cut being distance 1 apart. This simple idea defines a semi-metric \delta_{C} on V_{n} by (1) \delta_{C}(i,j)=\left\{\begin{array}[]{cl}1&\quad;\quad|C\cap\{i,j\}|=1,\cr 0&\quad;\quad|C\cap\{i,j\}|=0\text{ or }2.\end{array}\right. We call \delta_{C} the cut-metric corresponding to C . Obviously \delta_{C}=\delta_{V_{n}-C} . Let CUT_{n} denote the cut cone , defined as \displaystyle\text{CUT}_{n} \displaystyle=\left\{\sum_{C\subset V_{n}}w_{C}\,\delta_{C}\,\big|\,w_{C}\geq 0\right\}. A metric d on V_{n} lies in the cut cone if, by definition, it can be written as a linear combination of cut-metrics with non-negative coefficients: d=\sum_{C\subset V_{n}}w_{C}\cdot\delta_{C},\quad w_{C}\geq 0\text{ for all }C\subset V_{n}. The following beautiful theorem was proved in [ 2 ] . Theorem 1.1 . The metric space (V_{n},d) is isometric to a subspace of (\mathbb{R}^{m},d_{1}) if and only if d\in CUT_{n} . This theorem shifts the question of embeddability of a finite metric space (V_{n},d) into (\mathbb{R}^{m},d_{1}) , to the question of membership of d in the cut cone CUT_{n} . The latter is known to be NP-Complete decision problem: Theorem 1.2 (Avis-Deza [ 3 ] ) . The problem of determining if a metric d on V_{n} belongs to the cut cone CUT_{n} , is an NP-Complete decision problem. Building on this, and using the notions of promise decision problems and polynomial reduction, we prove what is the main result of this paper. Main Theorem . The problem of determining if a simple graph G with vertices V_{n}=\{1,\dots,n\} , admits an embedding \varphi:V_{n}\to\mathbb{R}^{m} so that the sphere-of-influence graph of \{\varphi(1),\dots,\varphi(n)\} with respect to the \ell_{1} -metric d_{1} on \mathbb{R}^{m} is isomorphic to G , is a Promise NP-Complete problem. Remark 1.1 . The notion of a Promise NP-Complete problem is a technical term explained in Section 2.2 . For now it suffices to say that every Promise NP-Complete problem reduces in polynomial time to any NP-Complete problem, and that therefore both types of problems are of equivalent computational complexity. 2. Background on Computational Complexity The exposition in this section follows standard texts in computation complexity theory. For decision/language problems we benefited from [ 1 , 11 , 15 , 16 ] , while for promise problems we followed [ 8 , 9 ] . 2.1. Promise and Decision Problems As is customary in computational complexity theory, we let \Sigma=\{0,1\} denote the “universal alphabet” and \Sigma^{\ast}=\{\varepsilon\}\cup\left(\cup_{n\geq 1}\Sigma^{\times n}\right) be its Kleene star, with \varepsilon the empty word. A promise problem B is a pair of disjoint subsets B_{\mathrm{Yes}},B_{\mathrm{No}}\subset\Sigma^{\ast} , with the possibility that B_{\mathrm{Yes}}\cup B_{\mathrm{No}}\neq\Sigma^{\ast} . The domain of the promise or simply the promise , denoted Dom (B) , is Dom (B)=B_{\mathrm{Yes}}\cup B_{\mathrm{No}} . Promise problems were introduced in [ 6 ] with a view toward applications in Public-Key Cryptography. They have since received considerable attention and applications elsewhere, see for instance [ 9 ] . A decision problem A is a promise problem for which Dom (A)=A_{\mathrm{Yes}}\cup A_{\mathrm{No}}=\Sigma^{\ast} . A decision problem is also referred to as a language recognition problem with the language L being L=A_{\mathrm{Yes}} , in which case the decision to make is whether word x\in\Sigma^{\ast} belongs to the language L . We will assume that the reader is familiar with the concept of a deterministic Turing machine , see for example [ 15 , Chapter 2] . 2.2. P versus NP, and Promise P versus Promise NP Following [ 9 , Definitions 2.4 and 2.5] , we make this definition. Definition 2.1 . Let A be a decision problem. (i) We say that A is of polynomial complexity , or in class P , if there exists a deterministic Turing machine M on \Sigma^{\ast} that halts in polynomial time, and accepts an x\in\Sigma^{\ast} if and only if x\in A_{\mathrm{Yes}} . (ii) A is non-deterministically polynomial or in class NP if there exists a polynomial p and a polynomial-time algorithm V such that for every x\in A_{\mathrm{Yes}} there exists a y\in\Sigma^{\ast} of length at most p(|x|) and with V(x,y)=1 (such a y is called an NP-witness for x ). Additionally, for every x\in A_{\mathrm{No}} and for any y\in\Sigma^{\ast} , V(x,y)=0 (saying that no witness y can accept an element in A_{\mathrm{No}} ). Similar notions of computational complexity can be formulated for promise problems, see [ 9 , Definition 2.31.] . Definition 2.2 . Let B be a promise problem. (i) We say that B is of promise polynomial complexity , or in class Promise P , if there exists a deterministic Turing machine M on \Sigma^{\ast} that halts in polynomial time for any x\in\mathrm{Dom}(B) and accepts an x\in\mathrm{Dom}(B) if and only if x\in B_{\mathrm{Yes}} . There is no requirement for the behavior of M on \Sigma^{\ast}-\mathrm{Dom}(B) . (ii) B is promise non-deterministically polynomial or in class Promise NP if there exists a polynomial p and a polynomial-time algorithm V such that for every x\in B_{\mathrm{Yes}} there exists a y\in\Sigma^{\ast} of length at most p(|x|) and with V(x,y)=1 . Additionally, for every x\in A_{\mathrm{No}} and for any y\in\Sigma^{\ast} , V(x,y)=0 . No requirements are made for how the algorithm V behaves on (x,y) with x\notin\mathrm{Dom}(B) . Remark 2.1 . Decision problems are special cases of promise problems,

Read the complete text