In the real world, many complex objects are modeled as graphs. For instance, social networks, protein interaction networks and chemical compounds are modeled as graphs. While many models utilize certain graphs, in some cases, uncertainty in data is inherent, thus it is convenient to model them as Uncertain Graphs. In this talk,
we study two fundamental problems in uncertain graphs, namely – (1) Domination in
uncertain graphs, and (2) Cores in uncertain graphs. We study both these problems on
uncertain graphs with two well-studied distribution models, namely – (1) linear reliable ordering (LRO) and independent distribution (IP) model.

In the LRO model We present FPT algorithms for the parameter treewidth of the input uncertain graph. Then, we use the result to obtain an FPT algorithm for the same problem on planar uncertain graphs for the parameter solution size. In contrast we show that when the vertex demands can be negative values, the problem turns out to be W[1]-hard for the parameter pathwidth of the input graph.
We then study the budgeted dominating set problem on uncertain graphs with IP (Independent Probability) model. We show that the problem is NP-complete even on trees with diameter at most four. Further, it is W[1]-hard for the parameter solution size on
trees. Then, we consider a variant of the above problem where all the edge probabilities are identical. We show that the problem is W[1]-hard for the parameter pathwidth of the input uncertain graph. We complement our hardness result by providing an FPT algorithm for the combined parameters treewidth of the input uncertain graph and the
solution size.

The threshold dominating set problem is a variant of the dominating set problem For the threshold dominating set problem on uncertain graphs, we seek a solution with size as small as possible. Another variant is the budgeted version of the threshold dominating set problem, called the budgeted-threshold dominating set problem. We study these problems on uncertain graphs with IP model. We show that these problems are
NP-hard even on graphs of constant treewidth.
Finally, we study k-core problem on uncertain graphs. We show that the problem is NP-hard when the distribution model is IP. Further, the problem is W[1]-hard for the parameter solution size. Then, we obtain an FPT algorithm for the parameter treewidth
of the input uncertain graph.