Consider a graph $G = (V, E)$ with $n$ vertices and $m$ edges. Each vertex $v_i$ can take positive value $a_i$ with probability $p_i$ and value $0$ with probability $1-p_i$.

The challenge is to assign weights $w_e$ to each edge to maximize the objective function $E = \sum_{e = \{i,j\}} w_e \Pr[X_i + X_j \geq w_e]$ where $\Pr[X_i + X_j \geq w_e]$ denotes the probability that that the sum of values taken by vertex $i$ and $j$ is greater than $w_e$. This is linear time to solve since there are only $3$ candidate values for $w_e$ which are $a_i, a_j, a_i + a_j$, so I can pick the one that maximizes $w_e \Pr[X_i + X_j \geq w_e]$ for each edge.

The additional constraint is that the weights $w_e$ need to be sub-additive, i.e., for any two edges $e'$ and $e''$ that "cover" edge $e$ meaning $e'$ and $e''$ include the vertices that make $e$, it holds that $w_e \leq w_{e'} + w_{e''}$.

Observe that the deterministic version of this stochastic problem where $p_i = 1$ is trivial since then I can just assign $w_e = a_i + a_j$ and the sub-additivity constraint is free since the function assigning the weights is exactly additive.

I strongly believe that this problem is NP-Hard (or #P-Hard?). I can show that for some special graphs like path graphs where each edge has degree at most $2$, this can be done in polynomial time because the number of sub-additive constraints is linear in the size of the graph but in general, even if there was an oracle that tells me the set of edges that participate in the optimal solution, there would be exponential constraints in the linear program that finds the optimal weights. It is also easy to solve if $p_i = p$ for each vertex $i$. Any pointers on potential approaches to show the hardness (or PTIME) would be greatly appreciated!

Edit : For people interested in the background of the problem, this is related to database query execution. Each vertex is a view that is materialized and each edge represents a query that can be answered using two views. The $w_e$ and $a_i$ are set up to represent the cost vs benefit of materializing the view to speed up query execution.

Edit 2 : I have realized a mistake in my supposed "proof" for path graphs of degree 2. I will ask that as a separate question and link this post there in order to leave the general problem.

  • $\begingroup$ Did you look at the additive case? $\endgroup$ – Radu GRIGore Apr 9 '18 at 10:23
  • $\begingroup$ @RaduGRIGore Do you mean strengthen subadditivity requirement to additive? I did not look but the complexity should still remain the same. The linear program solving the optimal prices will now also have a $we \geq w_{e′}+w_{e″}$ constraint. I feel the hardness comes not from subadditivity requirement but the bilinear objective. I haven't seen such problems being classified as NP-Hard which is why I am looking for some references. $\endgroup$ – karmanaut Apr 9 '18 at 19:07
  • $\begingroup$ Yes that's what I meant. I thought it might be easier to see what happens because you could have one {0,1}-variable per vertex (rather than per edge endpoint) and no explicit additivity constraint. But, yes, it's still bilinear. $\endgroup$ – Radu GRIGore Apr 10 '18 at 5:41

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.