Loop unrolling of UCA models: distance labeling
share
A proper circular-arc (PCA) model is a pair M = (C, A) where C is a circle and A is a family of inclusion-free arcs on C whose extremes are pairwise different. The model M represents a digraph D that has one vertex v(a) for each a ∈ A and one edge v(a) → v(b) for each pair of arcs a,b ∈ A(M) such that the beginning point of b belongs to a. For k ≥ 0, the k-th power D^k of D has the same vertices as D and v(a) → v(b) is an edge of D^k when a≠ b and the distance from v(a) to v(b) in D is at most k. A unit circular-arc (UCA) model is a PCA model U = (C,A) in which all the arcs have the same length ℓ+1. If ℓ, the length c of C, and the extremes of the arcs of A are integer, then U is a (c,ℓ)-CA model. For i ≥ 0, the model i × U of U is obtained by replacing each arc (s,s+ℓ+1) with the arc (s,s+iℓ+1). If U represents a digraph D, then U is k-multiplicative when i × U represents D^i for every 0 ≤ i ≤ k. In this article we design a linear time algorithm to decide if a PCA model M is equivalent to a k-multiplicative UCA model when k is given as input. The algorithm either outputs a k-multiplicative UCA model U equivalent to M or a negative certificate that can be authenticated in linear time. Our main technical tool is a new characterization of those PCA models that are equivalent to k-multiplicative UCA models. For k=1, this characterization yields a new algorithm for the classical representation problem that is simpler than the previously known algorithms.
READ FULL TEXT