Algorithms for Optimally Shifting Intervals under Intersection Graph Models

Abstract

We introduce Geometric Graph Edit Distance, a model for modifying geometric intersection graphs by moving objects. The objective is to obtain a graph in a prescribed class while minimising the total (weighted) moving distance of the objects. For weighted intervals of arbitrary length, we give a prune-and-search algorithm that renders their intersection graph complete in linear time. We adapt this approach to maximise the common intersection length of weighted intervals within a movement threshold in linear time. We also extend the algorithm for obtaining complete graphs to weighted axis-parallel rectangles of arbitrary size under the $L_1$ distance. For unweighted unit intervals, we give an $O(n\log n)$-time algorithm for obtaining a graph containing a $k$-clique. Lastly, we give $O(n)$-size linear programs for obtaining graphs in several classes, including edgeless, acyclic, $k$-clique-free and $k$-connected graphs.

Extended version of the IJTCS-FAW 2024 paper, with several corrections and proof improvements for complete graphs, k-cliques and the LP formulations. The added results cover maximum overlap within a movement threshold, weighted rectangles, r-connected k-clique-free graphs, and graphs with at most p components