Exact Algorithm for the Master Ring Problem

We are given a network that consists of $K$ rings, $R_1, R_2, dots, R_K$, with $n_1, n_2, ldots$, $n_K$ nodes, respectively. We aim to find a {em master ring} $M$ for the network, whenever such a ring exists. A master ring contains every node in the network exactly once and preserves the node ordering of each of the $K$ rings, either in the clockwise or counter-clockwise direction. 

This {em master ring problem (MRP)} often arises in optical network management. MRP defines a natural variant of the {em shortest common supersequence (SCS)} problem. We refer to this variant as {em 2Cyclic-SCS} and show that it is NP-hard. Our main result is an exact algorithm for MRP, whose running time approaches $Qcdot prod_{k=1}^K n_k/(sqrt{2})^K$ for some polynomial $Q$ as the $n_k$ values become large. 

For an important special case, known as the {em ring clearance problem}, our algorithm achieves this running time for rings of {em any} size $n_k geq 2$. This improves upon the naive brute-force algorithm, whose running time is $Pcdot prod_{k=1}^K (2n_k)$ for some polynomial $P$. To the best of our knowledge, this is the first algorithmic study of MRP. Our algorithm yields a polynomial time exact algorithm for the 2Cyclic-SCS problem, where the number of strings is some fixed constant.