Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Reachability Under Uncertainty   In this paper we introduce a new network reachability problem where the goal
is to find the most reliable path between two nodes in a network, represented
as a directed acyclic graph. Individual edges within this network may fail
according to certain probabilities, and these failure probabilities may depend
on the values of one or more hidden variables. This problem may be viewed as a
generalization of shortest-path problems for finding minimum cost paths or
Viterbi-type problems for finding highest-probability sequences of states,
where the addition of the hidden variables introduces correlations that are not
handled by previous algorithms. We give theoretical results characterizing this
problem including an NP-hardness proof. We also give an exact algorithm and a
more efficient approximation algorithm for this problem.

26
The categories of this paper are: bayes-an
8
The categories of this paper are: hep-ex
37
The categories of this paper are: supr-con
11
The categories of this paper are: hep-lat
16
The categories of this paper are: stat
35
The categories of this paper are: mtrl-th
25
The categories of this paper are: patt-sol
5
The categories of this paper are: gr-qc
23
The categories of this paper are: solv-int
15
The categories of this paper are: nucl-ex
34
The categories of this paper are: chem-ph
31
The categories of this paper are: ao-sci
30
The categories of this paper are: q-alg
10
The categories of this paper are: q-bio
3
The categories of this paper are: physics
19
The categories of this paper are: eess