On distance-preserving elimination orderings in graphs: Complexity and algorithms

For every connected graph G, a subgraph H of G is isometric if the distance between any two vertices in H is the same in H as in G. A distance-preserving elimination ordering of G is a total ordering of its vertex-set V(G), denoted (v1,v2,…,vn), such that any subgraph Gi=G∖(v1,v2,…,vi) with 1≤i<n is isometric. This kind of ordering has been introduced by Chepoi in his study on weakly modular graphs (Chepoi, 1998). We prove that it is NP-complete to decide whether such ordering exists for a given graph — even if it has diameter at most 2. Then, we prove on the positive side that the problem of computing a distance-preserving ordering when there exists one is fixed-parameter-tractable in the treewidth. Lastly, we describe a heuristic in order to compute a distance-preserving ordering when there exists one that we compare to an exact exponential time algorithm and to an ILP formulation for the problem.