Fully dynamic recognition of proper circular-arc graphs (Q2350902)

The dynamic recognition problem for a class of graphs \(C\) is the problem of maintaining a representation of a dynamically changing graph, while the graph belongs to \(C\). Its input is a graph \(G\) together with the sequence of operations that are to be applied on \(G\). A dynamic recognition algorithm is composed by the algorithm that builds the initial representation of \(G\) and the algorithms that apply each update on the representation. If recognition problem allows both incremental and decremental updates (incrementing/decrementing the size of \(G\)) it is called fully dynamic. This paper presents a fully dynamic algorithm for the recognition of proper circular-arc (PCA) graphs. Edge operations cost \(O(\log n)\) time, where \(n\) is the number of vertices of the graph, while vertex operations cost \(O(\log n+d)\) time, where \(d\) is the degree of the modified vertex. A circular-arc model is a family of arcs of some circle. A graph is said to admit a circular-arc model when its vertices are in a one-to-one correspondence with the arcs of the model in such a way that two vertices of the graph are adjacent if and only if their corresponding arcs have nonempty intersection. Those graphs that admit a circular-arc model are called circular-arc graphs. A circular-arc model is proper when none of its arcs is properly contained in some other arc of the model. A graph is a proper circular-arc (PCA) graph when it admits a proper circular-arc model, The authors also present incremental and decremental algorithms that work in \(O(1)\) time per inserted or removed edge and in \(O(d)\) time per vertex insertion. The following algorithms are easily obtainable from the above results: (i) fully dynamic connectivity and co-connectivity algorithms that work in \(O(\log n)\) time per operation, (ii) an \(O(\delta)\) time algorithm for determining if a PCA representation corresponds to a co-bipartite graph, where \(\delta\) is the maximum among the degrees of the vertices, (iii) an algorithm to find a minimal forbidden induced subgraph of a static graph in \(O(n+m)\) time.