Computational Considerations for Exclusive $(M,N)$-Transitive Augmentations

Abstract

Digraph $D$ is defined to be exclusive $(M,N)$-transitive if, for each pair of vertices $x$ and $y$, for each $xy$-path $P_1$ of length $M$, there is an $xy$-path $P_2$ of length $N$ such that $P_1\cap P_2=\{x,y\}$. It is proved that computation of a minimal edge augmentation to make $K$ exclusive $(M,N)$-transitive is NP-hard for $M>N\ge 2$, even if $D$ is acyclic. The corresponding decision problems are NP-complete. For $N=1$ and $D=(V,E)$ with $|V|=n$, an $O(n^{M+3})$ algorithm to compute the exclusive $(M,1)$-transitive closure of an arbitrary digraph is provided.