Abstrakt
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of geometric representations. We consider this problem for circular-arc graphs, where several arcs are predrawn and we ask whether this partial representation can be completed.
We show that this problem is NP-complete for circular-arc graphs, answering a question of Klavik et al. (2014). We complement this hardness with tractability results of the representation extension problem for various subclasses of circular-arc graphs.
We give linear-time algorithms for extending normal proper Helly and proper Helly representations. For normal Helly circular-arc representations we give an O(n(3))-time algorithm where n is the number of vertices.
Surprisingly, for Helly representations, the complexity hinges on the seemingly irrelevant detail of whether the predrawn arcs have distinct or non-distinct endpoints: In the former case the algorithm for normal Helly circular-arc representations can be extended, whereas the latter case turns out to be NP-complete. We also prove that the partial representation extension problem for unit circular-arc graphs is N P-complete.