I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. Giving a source node $s$ and a target node $t$. In this model, each time, we propose a simple path $p$, 1 of the edge $e_i$ in path $p$ will be removed with the probability based on the confidence score (the higher the score, the more chance it is being cut). For example, we propose path $p_1$ to cut, then the probability of edge $e_1$ being cut is $p_1 = \frac{c_1}{\sum_{i \in p}{c_i}}$. The problem is to find the optimal policy tree that suggests a path to cut at each step (disconnect $s$ and $t$). The optimal policy tree here must minimise the expected number of steps to cut the graph $G$ (minimise the depth policy tree).

For additional context, the model is inspired by the minimise connectivity test in the uncertain graph (which is why I think #P-hardness is worth looking at). They build a policy tree that minimises the expected number of steps to determine the connectivity of the Uncertain graph. The difference is their problem considers uncertain graphs (for ours, the edge is randomly chosen along the proposed path) and each step tests an edge instead of a path.

L. Fu, X. Fu, Z. Xu, Q. Peng, X. Wang, and S. Lu. Determining source–destination connectivity in uncertain networks: Modeling and solutions. IEEE/ACM Transactions on Networking, 25(6):3237–3252, 2017.

Any suggestion or direction for proof of the problem ?

  • $\begingroup$ Even representing a policy tree seems like it would take exponential space (just to represent all possibilities for which edges are cut). Any algorithm to output an exponential-length output must take exponential time. So this formulation does not seem promising. Perhaps it might be more useful to formulate the problem so that the goal of the algorithm is just to compute the optimal next step, instead of the entire policy tree? $\endgroup$
    – D.W.
    Commented May 9 at 17:30
  • $\begingroup$ I don't understand the definition of optimality. When can we stop the process of proposing paths? $\endgroup$
    – D.W.
    Commented May 9 at 17:36
  • $\begingroup$ The process of proposing paths stops when we have a cut (not necessarily a mincut). An optimal decision tree is a tree that has the minimum expected tree depth (minimising the number of paths needed to be proposed to cut the graph). The point of showing the hardness of the problem is to show that constructing the optimal tree is hard and hence we will need the heuristic algorithm (optimal next step algorithm could be a good heuristic). $\endgroup$ Commented May 10 at 3:01


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.