<p>Given a set of "required" weights for edges of a bipartite graph, I am looking for assignments to the nodes so that there is at least an edge carrying a weight from that set. Each edge can have possibly four weights as a+b, a-b, b-a, -a-b where the values on its endpoints are a and b. The values are allowed to be any real number.</p>

<p>For example, given {2,3,-5,8,9,12}, I can choose V1 = {4,10} and V2 = {1,2} where, out of 24 possible values over 6 edges (each edge has 4 values), we get all the required edge weights by<br>
 4 - 2 = 2 //
 4 - 1 = 3 //
-4 - 1 = -5 //
10 - 2 = 8 //
10 - 1 = 9 //
10 + 2 = 12 .</p>

<p>The reason that I stated the problem over a graph is that it seems to be similar to the Graph Turnpike problem studied by Feder and Motwani (On the graph turnpike problem, Information Processing Letters, 2009 - Elsevier).</p>

<p>I was wondering if this problem can be solved in polynomial time or reduced to another problem. </p>

CC BY-SA 3.0
2013-07-29T13:20:07.087Z
Gaussian elimination?
Jeffε
CC BY-SA 3.0
2013-07-29T14:36:58.980Z
do the assignments need to be integral ? or positive ?
Suresh Venkat
CC BY-SA 3.0
2013-07-29T15:40:47.103Z
I'm sorry. I did not mean that we know the labelings of the edges. We actually only have the set of weights and they have to be put on the edges. I'll edit the question.
Amin Jalali
CC BY-SA 3.0
2013-07-29T17:46:53.430Z
How are you preventing the trivial solution where you choose a single value $x$ from your set of allowed weights, use it as the weight of all edges, and set all vertex weights to $x/2$?
David Eppstein
CC BY-SA 3.0
2013-07-29T19:32:41.250Z
presumably (like in the normal turnpike) all edge weights are distinct and you're required to use exactly one element for each edge ?
Suresh Venkat
CC BY-SA 3.0
2013-07-30T02:03:55.217Z
I edited the question again. @DavidEppstein, we need to use all of the given weights and possibly have new ones.
Amin Jalali
CC BY-SA 3.0
2013-07-30T02:04:30.197Z
Also, in response to @SureshVenkat 's concern, we can actually use the given weights multiple times. I think this is making the problem different from turnpike, but my guess is that it is harder.
Amin Jalali
CC BY-SA 3.0
2013-08-02T05:36:28.430Z
I'm not clear on what are the inputs to the algorithm.  Is the input the set of required weights and $|V_1|$, $|V_2|$?  (And the graph is the complete bipartite graph over vertex sets $V_1,V_2$?)  Or is the input the set of required weights and a bipartite graph (which might or might not be complete)?  Or are we allowed to freely choose $|V_1|,|V_2|$ however we like?  (If the latter, the problem becomes trivial, so I'm guessing that's not what you meant.)
D.W.
CC BY-SA 3.0
2013-08-02T09:08:57.977Z
The input is the set of required weights. By using the word "required"  I mean that we are allowed to generate other weights as well (by assuming a complete bipartite graph) but we do not actually need them. 

The goal is to make this happen with minimal |V1| and |V2|; otherwise, as you said, it becomes trivial. I am not sure if there is a way to handle hard constraint on the size of V1 and V2 (my ultimate question), which is why I did not mention any constraint initially.
Amin Jalali
<np-hardness>
A version of bipartite graph turnpike problem
Amin Jalali
# A version of bipartite graph turnpike problem

(Asked by: username_0 on 2013-07-29)

Given a set of "required" weights for edges of a bipartite graph, I am looking for assignments to the nodes so that there is at least an edge carrying a weight from that set. Each edge can have possibly four weights as a+b, a-b, b-a, -a-b where the values on its endpoints are a and b. The values are allowed to be any real number.

For example, given {2,3,-5,8,9,12}, I can choose V1 = {4,10} and V2 = {1,2} where, out of 24 possible values over 6 edges (each edge has 4 values), we get all the required edge weights by  
4 - 2 = 2 //
4 - 1 = 3 //
-4 - 1 = -5 //
10 - 2 = 8 //
10 - 1 = 9 //
10 + 2 = 12 .

The reason that I stated the problem over a graph is that it seems to be similar to the Graph Turnpike problem studied by Feder and Motwani (On the graph turnpike problem, Information Processing Letters, 2009 - Elsevier).

I was wondering if this problem can be solved in polynomial time or reduced to another problem.

**Tags:** np-hardness

> **Comments:**
> **username_1**: Gaussian elimination?  
> **username_2**: do the assignments need to be integral ? or positive ?  
> **username_0**: I'm sorry. I did not mean that we know the labelings of the edges. We actually only have the set of weights and they have to be put on the edges. I'll edit the question.  
> **username_3**: How are you preventing the trivial solution where you choose a single value $x$ from your set of allowed weights, use it as the weight of all edges, and set all vertex weights to $x/2$?  
> **username_2**: presumably (like in the normal turnpike) all edge weights are distinct and you're required to use exactly one element for each edge ?  
> **username_0**: I edited the question again. @DavidEppstein, we need to use all of the given weights and possibly have new ones.  
> **username_0**: Also, in response to @SureshVenkat 's concern, we can actually use the given weights multiple times. I think this is making the problem different from turnpike, but my guess is that it is harder.  
> **username_4**: I'm not clear on what are the inputs to the algorithm.  Is the input the set of required weights and $|V_1|$, $|V_2|$?  (And the graph is the complete bipartite graph over vertex sets $V_1,V_2$?)  Or is the input the set of required weights and a bipartite graph (which might or might not be complete)?  Or are we allowed to freely choose $|V_1|,|V_2|$ however we like?  (If the latter, the problem becomes trivial, so I'm guessing that's not what you meant.)  
> **username_0**: The input is the set of required weights. By using the word "required"  I mean that we are allowed to generate other weights as well (by assuming a complete bipartite graph) but we do not actually need them.   The goal is to make this happen with minimal |V1| and |V2|; otherwise, as you said, it becomes trivial. I am not sure if there is a way to handle hard constraint on the size of V1 and V2 (my ultimate question), which is why I did not mention any constraint initially.  

---

## 0 answers

