Recognizing -Clique Extendible Orderings
A graph is -clique-extendible if there is an ordering of the vertices such that whenever two -sized overlapping cliques and have common vertices, and these common vertices appear between the two vertices in the ordering, there is an edge between and , implying that is a -sized clique. Such an ordering is said to be a -C-E ordering. These graphs arise in applications related to modelling preference relations. Recently, it has been shown that a maximum sized clique in such a graph can be found in time when the ordering is given. When is , such graphs are precisely the well-known class of comparability graphs and when is they are called triangle-extendible graphs. It has been shown that triangle-extendible graphs appear as induced subgraphs of visibility graphs of simple polygons, and the complexity of recognizing them has been mentioned as an open problem in the literature. While comparability graphs (i.e. -C-E graphs) can be recognized in polynomial time, we show that recognizing -C-E graphs is NP-hard for any fixed and co-NP-hard when is part of the input. While our NP-hardness reduction for is from the betweenness problem, for , our reduction is an intricate one from the -colouring problem. We also show that the problems of determining whether a given ordering of the vertices of a graph is a -C-E ordering, and that of finding an -sized (or maximum sized) clique in a -C-E graph, given a -C-E ordering, are complete for the parameterized complexity classes co-W[1] and W[1] respectively, when parameterized by . However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph.