论文标题
广义分数和分数分解的复杂性分析
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
论文作者
论文摘要
大树分解（HDS）以及更强大的广义高生高分子分解（GHD）以及更一般的分数大型高树分解（FHD）是成功使用的超图分解方法，用于解决结合性查询和解决约束满意度问题。相对于每种方法，每个HyperGraph $ h $都有一个宽度：其HyperTree宽度$ HW（H）$，其广义的Hypertree宽度$ GHW（H）$和其分数Hypertional Hypertree Width $ FHW（H）$。众所周知，$ hw（h）\ leq k $可以在固定$ k $的多项式时间内检查，同时检查$ ghw（h）\ leq k $是$ k \ geq 3 $的NP-Complete。固定$ K $检查$ fhw（h）\ leq k $的复杂性已经开放了十年。 我们通过表明检查$ fhw（h）\ leq k $是np complete，即使$ k = 2 $也是如此，我们解决了这个开放问题。相同的构造使我们还可以证明NP的完整性是检查$ ghw（h）\ leq k $ for $ k = 2 $。之后，我们确定有意义的限制，可以检查有限的$ ghw $或$ fhw $ tractable，或者允许有效地近似$ fhw $。
Hypertree decompositions (HDs), as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHDs) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Every hypergraph $H$ has a width relative to each of these methods: its hypertree width $hw(H)$, its generalized hypertree width $ghw(H)$, and its fractional hypertree width $fhw(H)$, respectively. It is known that $hw(H)\leq k$ can be checked in polynomial time for fixed $k$, while checking $ghw(H)\leq k$ is NP-complete for $k \geq 3$. The complexity of checking $fhw(H)\leq k$ for a fixed $k$ has been open for over a decade. We settle this open problem by showing that checking $fhw(H)\leq k$ is NP-complete, even for $k=2$. The same construction allows us to prove also the NP-completeness of checking $ghw(H)\leq k$ for $k=2$. After that, we identify meaningful restrictions which make checking for bounded $ghw$ or $fhw$ tractable or allow for an efficient approximation of the $fhw$.
