论文标题
恒定比率fpt的限制级别超图的宽度宽度参数
Constant ratio FPT approximation of hypertree width parameters for hypergraphs of bounded rank
论文作者
论文摘要
我们提出了一种算法，其输入是参数$ k $和$ r $和最多$ r $等级的HyperGraph $ h $。该算法要么返回最多$ 4K $或“否”的$ h $的树分解为$ h $。在后一种情况下，可以保证$ h $的高宽度大于$ k $。最重要的是，该算法的运行时间是$ k $和$ r $中的\ emph {fpt}。该方法延伸到分数高树的宽度，近似值略差（$ 4K+1 $而不是$ 4K $）。我们希望本文的结果将产生一个新的研究方向，其目的是针对限制性类别类别的fpt算法设计用于计算和近似的HyperTree宽度参数。
We propose an algorithm whose input are parameters $k$ and $r$ and a hypergraph $H$ of rank at most $r$. The algorithm either returns a tree decomposition of $H$ of generalized hypertree width at most $4k$ or 'NO'. In the latter case, it is guaranteed that the hypertree width of $H$ is greater than $k$. Most importantly, the runtime of the algorithm is \emph{FPT} in $k$ and $r$. The approach extends to fractional hypertree width with a slightly worse approximation ($4k+1$ instead of $4k$). We hope that the results of this paper will give rise to a new research direction whose aim is design of FPT algorithms for computation and approximation of hypertree width parameters for restricted classes of hypergraphs.
