关于紧套装包装的参数复杂性 关于紧套装包装的参数复杂性

科学领域:

• 理论计算机科学 理论计算机科学
• 计算复杂性理论 计算复杂性理论
• 算法设计和分析算法设计和分析

背景情况:

• 集合包装问题是一个基本的NP-hard优化问题,涉及到找到离散集合的最大集合.
• 参数化的复杂性分析了与参数相关的计算问题,旨在识别可处理的子问题.
• 之前的研究表明,参数化集合包装 (PSP) 不是固定参数可处理的 (FPT),除非P=NP,需要指数时间.

研究的目的:

• 从参数化的复杂性角度探索设置包装的可处理实例.
• 调查 Compact PSP 的复杂性,其中输入实例具有特定的结构性质 (紧性).

主要方法:

• 引入了PSP"紧"实例的概念,它是由基板的尺寸相对于基板数量的尺寸来定义的.
• 开发了一种新的小工具",兼容交叉集系统对",以证明硬度结果.
• 从参数化的复杂性应用技术来建立一个对立的紧型PSP.

主要成果:

• 建立了紧PSP的二分法:当参数k小时它是FPT,但当k大时它是W[1]-hard.
• 证明了 Compact PSP 不承认 $2^{o(k)} n^{O(1)}$ 的时间算法,假设指数时间假设 (ETH).
• 展示了现有的用于相关问题的构造,如设置覆盖,不扩展到紧型PSP.

结论:

• 集合包装实例的紧性显著影响其参数化的复杂性,导致一个明确的FPT/W[1]-硬边界.
• 新建的小工具对于证明Compact PSP的硬度至关重要,并为相关问题提供了洞察力.
• 该框架可以扩展到分析其他问题,例如 Compact k-VectorSum,可能会产生更好的下界.