标题： FPT 分参数化分数和广义超树宽度 显示英文标题

标题： FPT Parameterisations of Fractional and Generalised Hypertree Width

摘要： 我们提出了首个固定参数可解（fpt）算法，用于精确确定几个中心超图分解参数，包括广义超树宽、分数超树宽和自适应宽。 尽管这些度量在复杂性理论、数据库和约束满足中被广泛认可，但之前尚未有针对其中任何一种的精确fpt算法。 我们的结果适用于有界秩和有界度的超图类。 我们的方法扩展了最近一种用于树宽的算法（Bojańcyk & Pilipczuk, LMCS 2022），该算法利用了一阶二元关系（MSO）转换。 借助这一框架，我们克服了由超图带来的重大技术障碍，因为其结构分解在技术上比图的分解要复杂得多。 显示英文摘要

摘要： We present the first fixed-parameter tractable (fpt) algorithms for precisely determining several central hypergraph decomposition parameters, including generalized hypertree width, fractional hypertree width, and adaptive width. Despite the recognized importance of these measures in complexity theory, databases, and constraint satisfaction, no exact fpt algorithms for any of them had previously been known. Our results are obtained for hypergraph classes of bounded rank and bounded degree. Our approach extends a recent algorithm for treewidth (Boja\'ncyk & Pilipczuk, LMCS 2022) utilizing monadic second-order (MSO) transductions. Leveraging this framework, we overcome the significant technical hurdles presented by hypergraphs, whose structural decompositions are technically much more intricate than their graph counterparts.