# Parameterized Optimization in Uncertain Graphs--A Survey and Some Results
### Survey of Optimization Problems in Uncertain Graphs
Each possible world can be thought of as the set of edges which survive a disaster. Formally, an uncertain graph \(\mathcal{G}=(V,E,p)\) is a succinct description of the set of possible worlds that can arise due to a disaster in which an edge \(e\) is known to survive with probability \(p(e)\). The nature of dependence among the edge samples is used to model the nature of edge failures in the event of a disaster. As mentioned earlier, a fixed nature of dependence among the edge samples uniquely defines a probability distribution on the possible worlds. From this point, in this paper, we consider uncertain graphs where the uncertainty is on the survival of an edge (recall, the other possibility is on the uncertain edge weight). Further, all the results we present are for a fixed dependence among edge samples and such a fixed dependence among the edge samples is called a _distribution model_. Given the motivation of disasters, the distribution model is specified based on the dependence among the edge failures (recall, the failure probability of an edge \(e\) is \(1-p(e)\)). In this framework, for a fixed distribution model, the function to be optimized is the coverage function. **Definition 1** (Coverage within distance \(r\)). : _The input consists of an uncertain graph \(\mathcal{G}=(V,E,p)\) and an integer \(k\). The goal is to compute a \(k\)-sized vertex set \(S\) which maximizes the expected total weight of the vertices which are at distance at most \(r\) from \(S\). The expectation is over the possible worlds represented by the uncertain graph._  
Naturally, we refer to \(k\) as the budget, \(r\) as the radius of coverage (the number of hops in the network) and \(S\) is the set of vertices where facilities have to be located. For certain graphs and \(r=1\), the facility location with unreliable edges problem is the well-studied _budgeted dominating set_ problem which is known to be NP-hard [29]. The other case of natural interest is for \(r=\infty\). In this case, the coverage problem is to find a set \(S\) of \(k\) vertices so as to maximize the expected number of vertices connected to \(S\). In the case of certain graphs, this is polynomial time solvable as the problem is to find \(k\) connected components whose total vertex weight is the maximum. **Coverage in Social Networks. ** Coverage problems also have a natural interpretation in social networks. The dynamics of a social network based on the _word-of-mouth_ effect have been of significant interest in marketing and consumer research [30], where a social network is referred to as an interpersonal network. The work by [PERSON] and [PERSON] [30] state the different hypotheses for estimating the amount of uncertainty in a relationship between two persons in an interpersonal network. With the advent of social networks on the internet, the works of [PERSON] and [PERSON] [4; 31] formalized the questions relating to the effective marketing of a product based on interpersonal relationships in a social network. In 1969, the work of [PERSON] [32] had modeled the adoption of products as a diffusion process as a global phenomenon, independent of the interpersonal relationships between people in a society. [PERSON], [PERSON] and [PERSON] ([PERSON]) [14] brought together the earlier works on adoption of products in an interpersonal network and posed the question of selecting the most influential nodes in a social network with an aim to influence the maximum number of people to adopt a certain product or opinion. They considered the uncertainty in the social network to be the influence exerted by one individual on another individual and this is naturally modeled as an uncertain graph \(\mathcal{G}=(V,E,p)\). The propagation of influence is modeled as a diffusion process which is a function of time as in [PERSON] [32]. The influence maximization problems in KKT are considered under distribution models, which are described as diffusion phenomena, called the Independent Cascade model and the Linear Threshold Model.