An optimal algorithm for finding dominating cycles in circular-arc graphs (Q1186160): Difference between revisions

A subset of vertices of a graph is called a dominating cycle if the subgraph induced by it has a Hamiltonian cycle and every vertex not in the subset is adjacent to a vertex in the subset. It is well known that the problem of finding the minimum cardinality dominating cycle for a graph is \(NP\)-hard, but it is solvable in linear time if the graphs are 2-trees, 2-connected outerplanar graphs and series-parallel graphs. Let \(F\) be a family of arcs on the unit circle. A graph, called circular-arc graph, can be constructed from \(F\) as follows: each vertex corresponds to an arc of \(F\), two vertices are adjacent if and only if their corresponding arcs intersect. This paper presents an optimal \(\Theta(n\log n)\) time algorithm for finding a minimum cardinality dominating cycle in a circular-arc graph, where \(n\) is the number of vertices of the graph.