5

The answer to your updated Question (1) "When a problem is parameterized by something other than the size of a solution (and as a result, the size of a solution is still unbounded in terms of the parameter), then [is it] W[t]-hard for all t, at least?" is no. Independent Set for example is FPT with respect to the treewidth $\omega$ of the input ...


5

(This question was asked two years ago, but I'll post the answer for other people who may see this question.) In the Capacitated $k$-median problem we are given a set $F$ of facilities, each facility $f$ with a capacity $u_f \in \mathbb{Z}_{\geq0}$, a set $C$ of clients, a metric $d$ over $F\cup C$ and an upper bound $k$ on the number of facilities we can ...


Only top voted, non community-wiki answers of a minimum length are eligible