A Multivariate Approach for Weighted FPT Algorithms

We introduce a multivariate approach for solving weighted parameterized problems. Building on the

flexible

use of certain parameters, our approach defines a new general 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 wide applicability of our approach by solving the weighted variants of

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

a

W

n

O

(1)

, for some constant

a

 > 1, our approach yields running times of the form

b

s

n

O

(1)

, for some constant

b

 ≤ 

a

, 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. Clearly,

s

can be substantially smaller than

W

. Moreover, we give an example for a problem whose polynomial-time solvability crucially relies on our flexible (in lieu of a strict) use of parameters.

We further show, among other results, that

Weighted Vertex Cover

and

Weighted Edge Dominating Set

are solvable in times 1.443

t

n

O

(1)

and 3

t

n

O

(1)

, respectively, where

t

 ≤ 

s

is the minimum size of a solution.