论文标题
识别$ k $ -clique Extendible订购
Recognizing $k$-Clique Extendible Orderings
论文作者
论文摘要
图表为$ k $ clique-geldendsendsible，如果要订购顶点，以至于每当两个$ k $ sized的重叠集团$ a $ a $ a $ a $ a和$ b $都有$ k-1 $ common Pertices，并且这些共同的顶点出现在两个顶点$ a，b \ in（a \ setminus b）$ a $ $ a $ n use $ a $ n under under（b）$ a $ s $ in）之间。 $ b $，这意味着$ a \ cup b $是$（k+1）$大小的集团。据说这样的订购是$ k $ -c-e订购。这些图在与模型偏好关系有关的应用中产生。最近，已经表明，在给出订购时，可以在$ n^{o（k）} $时间中找到一个最大尺寸的集团。当$ k $为$ 2 $时，此类图就是众所周知的可比性类别类别，而当$ k $为$ 3 $时，它们被称为三角形扩展图。已经表明，三角形延伸图作为简单多边形的可见性图的诱导子图显示，并且识别它们的复杂性已被称为文献中的一个开放问题。 尽管可以在多项式时间内识别可比性图（即$ 2 $ -C-E图），但我们表明，对于任何固定的$ k \ geq 3 $，当$ k $ -c-e图均为NP-HARD，而当$ k \ geq 3 $和co-np-hard当$ k $是输入的一部分时。虽然我们的$ K \ geq 4 $减少了NP硬度来自中间问题，但对于$ k = 3 $，我们的减少是从$ 3 $颜色的问题中复杂的。我们还表明，确定图表顶点的给定排序是否为$ k $ -c-e订购，以及在$ k $ -c-e图中找到$ \ ell $ sized（或最大尺寸）集团的问题，给定的$ k $ -c $ -c-c-e订单是针对参数化的$ k $ -c-c-e订单，用于$ k $ -c-e gruending co-w [1]和w [1]和w [1]和[1]和[1]，是完整的。但是，我们表明，当图形的树宽参数化时，前者是固定参数可进行的。
A graph is $k$-clique-extendible if there is an ordering of the vertices such that whenever two $k$-sized overlapping cliques $A$ and $B$ have $k-1$ common vertices, and these common vertices appear between the two vertices $a,b\in (A\setminus B)\cup (B\setminus A)$ in the ordering, there is an edge between $a$ and $b$, implying that $A\cup B$ is a $(k+1)$-sized clique. Such an ordering is said to be a $k$-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 $n^{O(k)}$ time when the ordering is given. When $k$ is $2$, such graphs are precisely the well-known class of comparability graphs and when $k$ is $3$ 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. $2$-C-E graphs) can be recognized in polynomial time, we show that recognizing $k$-C-E graphs is NP-hard for any fixed $k \geq 3$ and co-NP-hard when $k$ is part of the input. While our NP-hardness reduction for $k \geq 4$ is from the betweenness problem, for $k=3$, our reduction is an intricate one from the $3$-colouring problem. We also show that the problems of determining whether a given ordering of the vertices of a graph is a $k$-C-E ordering, and that of finding an $\ell$-sized (or maximum sized) clique in a $k$-C-E graph, given a $k$-C-E ordering, are complete for the parameterized complexity classes co-W[1] and W[1] respectively, when parameterized by $k$. However we show that the former is fixed-parameter tractable when parameterized by the treewidth of the graph.
