The problem comes from network coding area. There is a wireless server that holds a set of data packets. There is a set of receivers, each already possesses a subset of the data packets, and wants all the remaining data packets. The server would like to broadcast a set of coded packets to the receivers to optimize a certain performance metric, where each coded packet is a linear combination of the data packets. I have proved that it is NP-hard to find the optimal coded packets when every coded packet can be received by every receiver. My question is that, is it still NP-hard to find the optimal coded packets when the receivers may randomly miss the coded packets? It is like "If making the optimal life-changing choice is already hard when you can foresee the future, is the choice still hard to make if you cannot foresee the future?" - toss a coin is out of the scope ...

Update: Thanks a lot for your attention and kindness to a newbie. Below is a more detailed version of my problem.

Original system model: we perform an iterative operation on a hyper-graph $\mathcal H(\mathcal V, \mathcal E)$: In each iteration, we use one color to color $\mathcal H$ in a way that at most one vertex $v$ of each hyper-edge $e$ is colored. (a.k.a. strong coloring). We then remove these vertices from $\mathcal H$.

Question-1: what is the optimal strong coloring solution for each iteration, so that the number of iterations is minimized?

_We have proved that this question is NP-hard to answer.

Now consider the following system model:

New system model: The same iterative strong coloring and removal process as above. However, when we try to remove a vertex, it has a nonzero probability of staying at each hyper-edge it belongs to. If it successfully stays at at least one hyper-edge, it will be uncolored, and will enter the next iteration. (When this happens, the vertex is only removed from some but not all the hyper-edges it belongs to.)

Question-2: What is the optimal strong coloring solution for each iteration, so that the expected number of iterations is minimized?

I conjecture that this question is also NP-hard to answer, but have no clue on how to prove it.

The problem comes from network coding area. There is a wireless server that holds a set of data packets. There is a set of receivers, each already possesses a subset of the data packets, and wants all the remaining data packets. The server would like to broadcast a set of coded packets to the receivers to optimize a certain performance metric, where each coded packet is a linear combination of the data packets. I have proved that it is NP-hard to find the optimal coded packets when every coded packet can be received by every receiver. My question is that, is it still NP-hard to find the optimal coded packets when the receivers may randomly miss the coded packets? It is like "If making the optimal life-changing choice is already hard when you can foresee the future, is the choice still hard to make if you cannot foresee the future?" - toss a coin is out of the scope ...

Update: Thanks a lot for your attention and kindness to a newbie. Below is a more detailed version of my problem.

Original system model: we perform an iterative operation on a hyper-graph $\mathcal H(\mathcal V, \mathcal E)$: In each iteration, we use one color to color $\mathcal H$ in a way that at most one vertex $v$ of each hyper-edge $e$ is colored. (a.k.a. strong coloring). We then remove these vertices from $\mathcal H$.

Question-1: what is the optimal strong coloring solution for each iteration, so that the number of iterations is minimized?

We have proved that this question is NP-hard to answer.

Now consider the following system model:

New system model: The same iterative strong coloring and removal process as above. However, when we try to remove a vertex, it has a nonzero probability of staying at each hyper-edge it belongs to. If it successfully stays at at least one hyper-edge, it will be uncolored, and will enter the next iteration. (When this happens, the vertex is only removed from some but not all the hyper-edges it belongs to.)

Question-2: What is the optimal strong coloring solution for each iteration, so that the expected number of iterations is minimized?

I conjecture that this question is also NP-hard to answer, but have no clue on how to prove it.

The problem comes from network coding area. A wireless server holds a set of data packets and would like to broadcast a set of coded packets to the receivers to optimize a certain performance metric, where each coded packet is a linear combination of the data packets. I have proved that it is NP-hard to find the optimal coded packets when every coded packet can be received by every receiver. My question is that, is it still NP-hard to find the optimal coded packets when the receivers may randomly miss the coded packets? It is like "If making the optimal life-changing choice is already hard when you can foresee the future, is the choice still hard to make if you cannot foresee the future?" - toss a coin is out of the scope ...

The problem comes from network coding area. There is a wireless server that holds a set of data packets. There is a set of receivers, each already possesses a subset of the data packets, and wants all the remaining data packets. The server would like to broadcast a set of coded packets to the receivers to optimize a certain performance metric, where each coded packet is a linear combination of the data packets. I have proved that it is NP-hard to find the optimal coded packets when every coded packet can be received by every receiver. My question is that, is it still NP-hard to find the optimal coded packets when the receivers may randomly miss the coded packets? It is like "If making the optimal life-changing choice is already hard when you can foresee the future, is the choice still hard to make if you cannot foresee the future?" - toss a coin is out of the scope ...

Update: Thanks a lot for your attention and kindness to a newbie. Below is a more detailed version of my problem.

Original system model: we perform an iterative operation on a hyper-graph $\mathcal H(\mathcal V, \mathcal E)$: In each iteration, we use one color to color $\mathcal H$ in a way that at most one vertex $v$ of each hyper-edge $e$ is colored. (a.k.a. strong coloring). We then remove these vertices from $\mathcal H$.

Question-1: what is the optimal strong coloring solution for each iteration, so that the number of iterations is minimized?

_We have proved that this question is NP-hard to answer.

Now consider the following system model:

New system model: The same iterative strong coloring and removal process as above. However, when we try to remove a vertex, it has a nonzero probability of staying at each hyper-edge it belongs to. If it successfully stays at at least one hyper-edge, it will be uncolored, and will enter the next iteration. (When this happens, the vertex is only removed from some but not all the hyper-edges it belongs to.)

Question-2: What is the optimal strong coloring solution for each iteration, so that the expected number of iterations is minimized?

I conjecture that this question is also NP-hard to answer, but have no clue on how to prove it.