We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: Longest Path, that is, given an undirected graph, find a maximum-length path in $G$. Longest Path is NP-hard in general but known to be solvable in $O(n^{4})$ time on $n$-vertex interval graphs. We show how to solve Longest Path on Interval Graphs, parameterized by vertex deletion number $k$ to proper interval graphs, in $O(k^{9}n)$ time. Notably, Longest Path is trivially solvable in linear time on proper interval graphs, and the parameter value $k$ can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems.
翻译：我们研究如何设计固定参数算法, 解决在多元时已知的可溶解的问题。 主要动机是获取效率更高的算法, 解决不具有吸引力的多元运行时间的问题。 在这里, 我们关注一个基本的图形问题 : 最长路径, 即, 给一个未定向的图形, 找到一个以$G$为单位的最大长度路径。 最长路径一般是 NP- 硬的, 但已知在$O (n ⁇ 4}) 时间上可以溶解于 $O (n ⁇ 4}), 而在 $n- verdex 间隔图中, $n- verdex 时间。 我们展示了如何解决Interval 图形中最长路径, 以 $k$( k$) 参数删除为参数, 以 $( k) $( k) $( nä9} ) 时间为单位。 值得注意的是, 最长路径在适当的间断图中, 直线时间中, 参数值可以接近于 4 。 从更一般的参数值 。 我们认为, 使用参数化复杂程度的分析可以帮助人们更清楚地了解 如何分析 。
相关内容
微信扫码咨询专知VIP会员