1
$\begingroup$

So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth. As far as I know, this breaks down in the weighted case since the O(k^2) in your final solution could all be very low value.

Has there been work done in applying bidimensionality to weighted problems?

$\endgroup$
  • $\begingroup$ This depends on the problem and the weight function. For example, if you allow strictly positive integer weights, in minimization problems, $k$ is a lower bound on the number of vertices/edges to take (since every vertex has a weight $\ge 1$), so with a very small change to the unweighted case, the weighted variance works. Be more specific and clarify your question further (e.g. define a problem you have in mind and corresponding weight function for the given instance). $\endgroup$ – Saeed Aug 27 at 14:37
  • $\begingroup$ @Saeed so I guess any problem for which the difference between the cheapest and most expensive vertex is arbitrarily large. $\endgroup$ – Hao S Aug 27 at 17:47
  • 1
    $\begingroup$ You should be more specific, it could be dependent on the existing algorithms for the problem. But generally, if the minimum weight is one, then any minimization problem that looks for a solution of size $k$ can simply exploit the fact that a solution of size $k$ has at most $k$ vertices (e.g. vertex cover), then conclude that the grid size cannot be big. But if $k$ is not the parameter or you allow epsilon weights, then it is another story (in such cases scaling technique might help to provide a good approximation). $\endgroup$ – Saeed Aug 29 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.