A multivariate framework for weighted FPT algorithms

作者：Shachnai Hadas; Zehavi Meirav^*

来源：Journal of Computer and System Sciences, 2017, 89: 157-189.

DOI：10.1016/j.jcss.2017.05.003

• Parameterized algorithm
• Weighted graph problem
• Vertex cover
• 3-Hitting set
• Edge dominating set

We introduce a multivariate approach for solving weighted parameterized problems. By allowing flexible use of parameters, our approach defines a framework for applying the classic bounded search trees technique. In our model, given an instance of size n of a minimization/maximization problem, and a parameter W >= 1, we seek a solution of weight at most/at least W. We demonstrate the usefulness of our approach in solving VERTEX COVER, 3-HITTING SET, EDGE DOMINATING SET and MAX INTERNAL OUT-BRANCHING. While the best known algorithms for these problems admit running times of the form c(W)n(0(1)), for some c > 1, our framework yields running times of the form c(s)n(0(1)), where s <= W is the minimum size of a solution of weight at most/at least W. If no such solution exists, s = min{W, m}, where m is the maximum size of a solution. In addition, we analyze the parameter t <= s, the minimum size of a solution.

• 出版日期2017-11