Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width

摘要

Graphs of clique-width at most k were introduced by Courcelle, Engelfriet and Rozenberg (1993) as graphs which can be defined by k-expressions based on graph operations which use k vertex labels. In this paper we show that the (q, q - 4) graphs are of clique width at most q and P_4-tidy graphs are of clique-width at most 4. Furthermore, the k-expression (for k = 4 or k = q) associated with such a graph can be found in linear time.rn(q,q - 4) graphs were introduced by Babel and Olariu (1995) and extends the class of P_4-sparse graphs. P_4-sparse graphs were introduced by Hoang (1985) and are widely studied because of their applications in areas such as scheduling, clustering and computational semantics. Another extension of P_4-sparse graphs are the Pi-tidy graphs which were introduced by Rusu (1995).rnFurthermore, we show that the class of LinEMSOL(T_(1, L)) optimization problems is solvable in O(f(|V|, |E|)) time on a class of graphs of clique-width at most k in which for every graph G an expression defining it can be constructed in O(f(|V|, |E|)) time. By the above this applies in particular to (q, q - A) graphs, P_4-tidy graphs and P_4-sparse graphs with f linear.rnFinally, we show that the above results cannot be extended to MSOL(T_2) decision and optimization problems on the vocabulary T_2 which allow edges to be considered as elements of the domains of the graphs in question, and by that, allow quantifying over edges in addition to quantifying over vertices.