<p>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.</p>
<p>Has there been work done in applying bidimensionality to weighted problems?</p>

CC BY-SA 4.0
2020-08-27T14:37:00.053Z
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).
Saeed
CC BY-SA 4.0
2020-08-27T17:47:56.613Z
@Saeed  so I guess any problem for which the difference between the cheapest and most expensive vertex is arbitrarily large.
Hao S
CC BY-SA 4.0
2020-08-29T09:39:17.637Z
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).
Saeed
<cc.complexity-theory><approximation-algorithms><planar-graphs><treewidth>
Can the theory of Bidimensionality be applied to weighted instances of a problem?
Hao S
# Can the theory of Bidimensionality be applied to weighted instances of a problem?

(Asked by: username_0 on 2020-08-26)

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?

**Tags:** cc.complexity-theory, approximation-algorithms, planar-graphs, treewidth
> **Comments:**
> **username_1**: 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).  
> **username_0**: @Saeed  so I guess any problem for which the difference between the cheapest and most expensive vertex is arbitrarily large.  
> **username_1**: 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).  

---

## 0 answers

