On the Complexity of Minimising the Moving Distance for Dispersing Objects

Graph modification is a fundamental topic to address graph similarity and dissimilarity, where a given graph is deformed by adding or deleting vertices or edges to satisfy a specific non-trivial graph property, while minimising the cost of edit operations. The problem of determining this cost is commonly known as graph modification problem (GMP) and has applications in various disciplines, such as computer vision [3], network interdiction [15], and molecular biology [14]. GMPs are often categorised into vertex and edge modification problems, with edit operations restricted to the vertex and edge sets, respectively.

The cost of a single edit operation in a GMP is often determined by the specific application. In theoretical studies, a unit-cost model is often assumed, where each addition or deletion of a vertex or edge has a uniform cost. However, for such models, it is known that determining whether a graph can be modified to obtain a member of a given class is $\mathrm{𝖭𝖯}$-hard for a wide range of graphs and classes [19, 2, 12, 25]. These negative bounds of GMPs motivate alternative formulations for graph editing that consider domain-specific constraints and cost measures.

The choice of edit operations and their associated costs is a crucial aspect of GMPs, as different formulations capture different structural properties and computational challenges. Analogous to string similarity analysis, where modifications are based on biologically significant operations such as DNA mutations and repeats [20], graph modification problems should reflect the inherent constraints and structural properties of the graphs being studied. In particular, geometric intersection graphs (hereafter intersection graphs) provide a suitable framework for studying GMPs for scenarios where graphs represent spatial relationships (see, e.g., [23, 6, 10]). Given a collection of geometric objects $𝒮$, an intersection graph $G(𝒮)$ is a graph where there is a one-to-one correspondence between the vertex set $V(G(𝒮))$ and $𝒮$, and two vertices are adjacent if and only if their corresponding objects intersect. This model includes many well-known graph classes, such as interval graphs and disk graphs. These graphs can be frequently found in real-world applications such as network modelling and bioinformatics [22].

Motivated by this context, this paper investigates GMPs for intersection graphs. In this context, two natural questions arise:

1. 1.

   Are standard graph edit operations suitable for modifying intersection graphs?

2. 2.

   How can the geometric properties of objects be exploited to overcome the hardness of GMPs?

To answer these questions, we introduce Geometric Graph Edit Distance, a model for modifying intersection graphs from a geometric perspective.

In the intersection graph model, a natural edit operation is to move the objects in $𝒮$. We treat this movement as a graph edit operation and focus on minimising the cost required to modify an intersection graph so that the resulting graph is in a specific graph class. The cost is quantified by the total moving distance, which is the sum of the distances by which objects in $𝒮$ are moved. More precisely, we define the problem as follows:

We assume that $\mathrm{\Pi }$ is given by an oracle, i.e. we have an algorithm to determine whether the intersection graph $G(𝒮)$ is in $\mathrm{\Pi }$.

This section provides the main definitions used in the paper, referencing geometry, graph, and convexity terminology from textbooks [24, 4, 7, 1].

We show that a graph in ${\mathrm{\Pi }}_{\text{edgeless}}$ can be obtained in $O(n\log n)$ time given a collection of $n$ unit intervals. We start by defining a problem that we call Interval Dispersal and then use the algorithm designed to obtain a graph in ${\mathrm{\Pi }}_{\text{edgeless}}$, ${\mathrm{\Pi }}_{\text{acyc}}$ and $\overline{{\mathrm{\Pi }}_{k\text{-clique}}}$. Interval Dispersal receives as input a collection $ℐ$ of $n$ intervals and a real $s\ge 1$, and asks for the minimum value of the total moving distance to obtain a collection ${ℐ}^{\prime }$ that satisfies $c(I_j^{\prime })-c(I_i^{\prime })\ge s$ for each $I_i^{\prime },I_j^{\prime }\in {ℐ}^{\prime }$, . When $s=1$, Interval Dispersal is equivalent to Geometric Graph Edit Distance on unit interval graphs and ${\mathrm{\Pi }}_{\text{edgeless}}$. For simplicity, the intervals are assumed to be open. This avoids the need to address infinitesimally small distances required to separate closed intervals. We must first introduce some basic definitions and notation to describe the algorithm. Given a collection of $n$ intervals $ℐ=\{I_1,\mathrm{\dots },I_n\}$, let $D=(d_1,\mathrm{\dots },d_n)$ be a vector such that $d_i$ is the moving distance applied to $I_i$. We denote by ${ℐ}^D=\{I_1^D\mathrm{\dots },I_n^D\}$ the collection of intervals such that $c(I_i^D)=c(I_i)+d_i$. The set $𝒟(ℐ)\subseteq {ℝ}^n$ is the set of vectors that describe the moving distance applied to intervals such that the condition of Interval Dispersal is satisfied. In other words, for all $D=(d_1,\mathrm{\dots },d_n)\in 𝒟(ℐ)$, $c(I_j^D)+c(I_i^D)\ge s$ holds for . We use ${𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)\subseteq 𝒟(ℐ)$ to denote the subset of vectors in $𝒟(ℐ)$ that minimises the total moving distance applied to intervals; i.e. ${𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)=\{D=(d_1,\mathrm{\dots },d_n)\in 𝒟(ℐ)\mid {\sum }_{1\le i\le n}|d_i|={\min }_{D^{\prime }=(d_1^{\prime },\mathrm{\dots },d_n^{\prime })\in 𝒟(ℐ)}{\sum }_{1\le i\le n}|d_i^{\prime }|\}$.

Intuitively, we aim to find a vector $D\in {𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)$ to move each interval so that the distance between each pair of intervals is at least $s$. Given an arbitrary $D\in {𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)$, the order of ${ℐ}^D$ may be different from the order of $ℐ$. However, it was previously shown [16] that there is always a vector $D\in {𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)$ such that the order of ${ℐ}^D$ preserves the order of $ℐ$. This implies that there always exists an optimal solution of Interval Dispersal for which checking the inequality $(c(I_{i+1})+d_{i+1})-(c(I_i)+d_i)\ge s\text{ for }\le i\le n-1$ is sufficient.

We now define the equispace function, which moves intervals so that the distance between their centres is exactly $s$, maintaining the order induced by interval centres.

By the above, $E_x(ℐ)\in 𝒟(ℐ)$ for all $x\in ℝ$. Moreover, $c(I_{i+1}^{E_x(ℐ)})-c(I_i^{E_x(ℐ)})=s$ for all $1\le i\le n-1$. We first prove that for certain collections of intervals, minimising $E$ gives a vector contained in ${𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)$.

We define the set of breakpoints of $E(ℐ,x)$ to be the set $B_{ℐ}=\{b_1^{ℐ},\mathrm{\dots },b_n^{ℐ}\}=\{c(I_i)+(n-i)s\mid I_i\in ℐ,\mathrm{\hspace{0.25em}1}\le i\le n\}$. Given a collection of intervals $ℐ$, we define the equispace function $E(ℐ,x)$ as a sequence of linear functions $E_1(ℐ,x),\mathrm{\dots },E_{|ℐ|+1}(ℐ,x)$. The slope of $E_i(ℐ,x)$ is less than the slope of $E_j(ℐ,x)$ for . Since the equispace function is convex and piecewise linear, the points that minimise $E$ are located within a range $b_{\mathrm{\ell }}\le x\le b_r$, where $b_{\mathrm{\ell }}\le b_r$ and $b_{\mathrm{\ell }},b_r\in B_{ℐ}$. We prove that $b_{\mathrm{\ell }}$ and $b_r$ can be easily found.

By Lemma 3, the minimum value of $E$ for an arbitrary collection of intervals $ℐ$ is given by the median value(s) of $B_{ℐ}$. We now show which collections allow minimising $E$ to obtain a vector in ${𝒟}^{\mathrm{𝑜𝑝𝑡}}(ℐ)$, characterised as follows:

In this section we show that Geometric Graph Edit Distance is strongly $\mathrm{𝖭𝖯}$-hard on weighted interval graphs for ${\mathrm{\Pi }}_{\text{edgeless}}$. We show a reduction from 3-Partition [13]. 3-Partition receives as input a set $A$ of $3m$ elements, a bound $B\in {\mathbb{Z}}^{+}$ and a size $s(a)\in {\mathbb{Z}}^{+}$ such that and ${\sum }_{a\in A}s(a)=mB$, and the task is to decide whether $A$ can be partitioned into $m$ disjoint sets $A_1,\mathrm{\dots },A_m$ such that for $1\le i\le m$, $|A_i|=3$ and ${\sum }_{a\in A_i}s(a)=B$.

Given an instance $(A,B,s)$ of 3-Partition, we construct a collection of intervals ${ℐ}_A$ and show that $A$ can be partitioned if and only if ${ℐ}_A$ can be modified so that $G({ℐ}_A)\in {\mathrm{\Pi }}_{\text{edgeless}}$ with at most total moving distance $T$. Given two intervals $I,I^{\prime }$ such that $c(I)\le c(I^{\prime })$, we say that $I$ and $I^{\prime }$ intersect if .

We show the construction of ${ℐ}_A$ (see Figure 1). We define ${ℐ}_A$ as the collection $ℐ\cup {ℐ}^s\cup {ℐ}^b$ where $ℐ=\{I_1,\mathrm{\dots },I_{3m}\},{ℐ}^s=\{I_1^s,\mathrm{\dots },I_{m-1}^s\},{ℐ}^b=\{I_{\mathrm{\ell }},I_r\}$ and,

1. (i)

   for $1\le i\le 3m$, $I_i$ is an interval such that $\mathrm{len}(I_i)=s(a_i)$ and $c(I_i)=-s(a_i)/2$ (that is, $r(I_i)=0$),

2. (ii)

   for $1\le i\le m-1$, $I_i^s$ is an interval where $\mathrm{len}(I_i^s)=B$ and $c(I_i^s)=(2i-1)B+B/2$ and

3. (iii)

   $I_{\mathrm{\ell }}$ and $I_r$ are intervals such that $\mathrm{len}(I_{\mathrm{\ell }})=\mathrm{len}(I_r)=3B{m}^2+{\max }_{a\in A}s(a)$, $c(I_{\mathrm{\ell }})=-3B{m}^2/2$ and $c(I_r)=(2m-1)B+3B{m}^2/2$.

For an interval $I\in {ℐ}_A$, we define the moving distance function $d_I:ℝ\to ℝ$ as:

Given an instance $(A,B,s)$ of 3-Partition, we show the following properties.

We note that Lemma 14 works for any partition of $A$ as described above, even without the restrictions of the 3-Partition output.

Lastly, we remark that the polynomial construction of ${ℐ}_A$ is straightforward by iterating over $A$ and following the definitions given at the beginning of the section. We summarise the main result of this section as follows:

We notice that Theorem 16 can be extended to show that obtaining graphs in ${\mathrm{\Pi }}_{\text{acyc}}$ and $\overline{{\mathrm{\Pi }}_{k\text{-clique}}}$ is also strongly $\mathrm{𝖭𝖯}$-hard.

In particular, when obtaining a graph in $\overline{{\mathrm{\Pi }}_{k\text{-clique}}}$, we create $k-1$ overlapping copies of the intervals in ${ℐ}^s\cup {ℐ}^b$ and add $k-1$ overlapping intervals of size $B$ into the spaces between intervals of ${ℐ}^s\cup {ℐ}^b$ with the same moving distance function. Any interval forms a $k$-clique with the $k$ copies of overlapping intervals. Consequently, moving the intervals of $ℐ$ with total moving distance of at most $3B{m}^2$ is equivalent to removing all $k$-cliques from ${ℐ}_A$ with at most the same distance. Moreover, by the chordality of interval graphs, it is sufficient to obtain a graph in $\overline{{\mathrm{\Pi }}_{k\text{-clique}}}$ when $k=3$ for class ${\mathrm{\Pi }}_{\text{acyc}}$. As a result, Corollary 17 is obtained.

In this section, we deal with the minimax version of Geometric Graph Edit Distance, defined as follows:

We show that minimax-Geometric Graph Edit Distance is strongly $\mathrm{𝖭𝖯}$-hard on unit disk graphs for $\mathrm{\Pi }={\mathrm{\Pi }}_{\text{edgeless}}$ over the $L_1$ and $L_2$ distances by reducing from Planar 3-SAT. Specifically, we show a proof for Theorem 18.

Due to space constraints, we only give an overview of the reduction. The complete reduction and proofs can be found in the full-version of the paper [17].

The main contribution of this paper is two-fold. First, we continued the study of Geometric Graph Edit Distance originally presented in [16], showing complexity results for obtaining graphs in several classes for sparse graphs on interval graphs. In particular, we showed that obtaining a graph in ${\mathrm{\Pi }}_{\text{edgeless}}$, ${\mathrm{\Pi }}_{\text{acyc}}$ and $\overline{{\mathrm{\Pi }}_{k\text{-clique}}}$ is solvable in $O(n\log n)$ time on unit interval graphs. In contrast, we showed that the problem becomes strongly $\mathrm{𝖭𝖯}$-hard on weighted interval graphs for the same classes. Second, we defined minimax-Geometric Graph Edit Distance as a variation of the above problem and showed that it is strongly $\mathrm{𝖭𝖯}$-hard for ${\mathrm{\Pi }}_{\text{edgeless}}$ on weighted unit disk graphs over the $L_1$ and $L_2$ distances.

There are several directions for further research. Our results provide a comprehensive picture of the complexity of Geometric Graph Edit Distance on interval graphs. In particular, we showed that the problem becomes hard even in lower dimensions when the input is not restricted by interval size and distance weight. As a result, a potential future work is to study the complexity when exclusively one of the restrictions is applied. Another interesting direction is to study the model for ${\mathrm{\Pi }}_{\text{edgeless}}$ in higher dimensions. Related works [10, 11, 9] suggest that our model on more complex intersection graphs becomes intractable for some of the graph classes presented in this work. In general, we deal with the edit operation that moves the objects of the given intersection graph. However, the model is not restricted to this operation. Determining Geometric Graph Edit Distance using other geometric edit operations (such as shrinking or rotating objects) is left for future research for all intersection graphs and graph classes presented in this work.