论文标题
包装$ k_r $ s在有限度图中
Packing $K_r$s in bounded degree graphs
论文作者
论文摘要
我们研究了在固定最大程度$δ$的无向图中找到最大信号$ $ $ cliques的最大信号性集的问题，但该集合中的集合是顶点disjoint或edge-disjoint。如果$δ= 3 $（$δ= 4 $），则以$ r = 3 $而闻名，即顶点 - disjoint（edge-diserjoint）问题在线性时间内可以解决，但如果$δ\ geq 4 $（$δ\ geq 5 $），则可以解决apx-hard。 我们将这些结果推广到任意但固定的$ r \ geq 3 $，并为最大程度$δ$的顶点和边缘 - 偶数变体提供了完整的复杂性分类。 具体而言，我们表明，如果$Δ<3r/2-1 $，如果$Δ<5r/3-1 $，则可以在线性时间内解决顶点问题问题，如果$Δ<5r/3-1 $，如果$Δ\ geq \ geq \ geq \ geq \ geq \ geq \ geq \ lceq \ lceil 5r/3 \ rceil -rceil -rceil -rceil -1 $。我们还表明，如果$ r \ geq 6 $，那么上述含义也适用于边缘 - 界问题问题。如果$ r \ leq 5 $，则如果$Δ<3r/2-1 $，则可以在线性时间解决边缘 - 划分问题，如果$δ\ leq 2r -2 $，则可以在多项式时间内解决，如果$Δ> 2r -2 $，则可以在多项式时间内解决。
We study the problem of finding a maximum-cardinality set of $r$-cliques in an undirected graph of fixed maximum degree $Δ$, subject to the cliques in that set being either vertex-disjoint or edge-disjoint. It is known for $r=3$ that the vertex-disjoint (edge-disjoint) problem is solvable in linear time if $Δ=3$ ($Δ=4$) but APX-hard if $Δ\geq 4$ ($Δ\geq 5$). We generalise these results to an arbitrary but fixed $r \geq 3$, and provide a complete complexity classification for both the vertex- and edge-disjoint variants in graphs of maximum degree $Δ$. Specifically, we show that the vertex-disjoint problem is solvable in linear time if $Δ< 3r/2 - 1$, solvable in polynomial time if $Δ< 5r/3 - 1$, and APX-hard if $Δ\geq \lceil 5r/3 \rceil - 1$. We also show that if $r\geq 6$ then the above implications also hold for the edge-disjoint problem. If $r \leq 5$, then the edge-disjoint problem is solvable in linear time if $Δ< 3r/2 - 1$, solvable in polynomial time if $Δ\leq 2r - 2$, and APX-hard if $Δ> 2r - 2$.
