咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >On the Descriptive Complexity ... 收藏

On the Descriptive Complexity of Color Coding

作     者:Bannach, Max Tantau, Till 

作者机构:Univ Lubeck Inst Theoret Comp Sci D-23562 Lubeck Germany 

出 版 物:《ALGORITHMS》 (算法)

年 卷 期:2021年第14卷第3期

页      面:96页

核心收录:

学科分类:0301[法学-法学] 03[法学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

主  题:color coding descriptive complexity fixed-parameter tractability quantifier elimination para-AC(0) 

摘      要:Color coding is an algorithmic technique used in parameterized complexity theory to detect small structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pattern. We transfer color coding to the world of descriptive complexity theory by characterizing-purely in terms of the syntactic structure of describing formulas-when the powerful second-order quantifiers representing a random coloring can be replaced by equivalent, simple first-order formulas. Building on this result, we identify syntactic properties of first-order quantifiers that can be eliminated from formulas describing parameterized problems. The result applies to many packing and embedding problems, but also to the long path problem. Together with a new result on the parameterized complexity of formula families involving only a fixed number of variables, we get that many problems lie in FPT just because of the way they are commonly described using logical formulas.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分