<p>Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around).</p>
<p>My objective is to do something similar to the following: If the unweighted case cannot be approximated better than say <span class="math-container">$O(n^3)$</span> where <span class="math-container">$n$</span> is the number of nodes in the graph; I want a reduction that says you if you can do the weighted variant with <span class="math-container">$O(n^k))$</span>, then you can do the unweighted one with <span class="math-container">$O(n^{k-c})$</span> and thus you can't do the weighted one with a ratio better than <span class="math-container">$O(n^{3+c})$</span>.</p>
<p>PS: Sorry for being vague here. I haven't asked too many questions in StackExchange. So, I am not sure how exactly it works.</p>
<p>I searched around for this; everything I can find is a reduction from the weighted case to the unweighted case.</p>
<p>I also do not want weights to be assigned as 1 for the reduction as I want c to be some useful number.</p>

CC BY-SA 4.0
2022-10-20T00:52:02.643Z
Well, there are problems whose unweighted versions can be approximated (in poly time) with much better approximation ratios than the weighted versions.  But I don't know of any such results that are shown via the kind of reduction you ask for.
Neal Young
CC BY-SA 4.0
2022-10-20T17:57:41.970Z
Typically, for most problems in discrete optimization, the approximation for weighted is similar to that of unweighted even though it is sometimes more difficulty to handle the weighted case. There are only a few "natural" examples that I am aware of where the weighted case is provably harder than the unweighted --- there must be something specific about the problem structure that allows this. Given this, the type of reduction you are looking for is perhaps not so easy to find.
Chandra Chekuri
<reductions><approximation-hardness>
Reduction from unweighted graphs to weighted graphs?
Nithish kumar
# Reduction from unweighted graphs to weighted graphs?

(Asked by: username_0 on 2022-10-19)

Are there any examples where you take a problem for the unweighted case and reduce it to the weighted case? (Not the other way around).

My objective is to do something similar to the following: If the unweighted case cannot be approximated better than say $O(n^3)$ where $n$ is the number of nodes in the graph; I want a reduction that says you if you can do the weighted variant with $O(n^k))$, then you can do the unweighted one with $O(n^{k-c})$ and thus you can't do the weighted one with a ratio better than $O(n^{3+c})$.

PS: Sorry for being vague here. I haven't asked too many questions in StackExchange. So, I am not sure how exactly it works.

I searched around for this; everything I can find is a reduction from the weighted case to the unweighted case.

I also do not want weights to be assigned as 1 for the reduction as I want c to be some useful number.

**Tags:** reductions, approximation-hardness

> **Comments:**
> **username_1**: Well, there are problems whose unweighted versions can be approximated (in poly time) with much better approximation ratios than the weighted versions.  But I don't know of any such results that are shown via the kind of reduction you ask for.  
> **username_2**: Typically, for most problems in discrete optimization, the approximation for weighted is similar to that of unweighted even though it is sometimes more difficulty to handle the weighted case. There are only a few "natural" examples that I am aware of where the weighted case is provably harder than the unweighted --- there must be something specific about the problem structure that allows this. Given this, the type of reduction you are looking for is perhaps not so easy to find.  

---

## 0 answers

