{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T20:27:07Z","timestamp":1771705627480,"version":"3.50.1"},"reference-count":48,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,12,19]],"date-time":"2019-12-19T00:00:00Z","timestamp":1576713600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) model. We present an FPT algorithm parameterized by the product of treewidth and max-degree for maximizing expected coverage in an uncertain graph under the RF model. We then consider the problem of finding the maximal core in a graph, which is known to be polynomial time solvable. We show that the Probabilistic-Core problem is polynomial time solvable in uncertain graphs under the LRO model. On the other hand, under the RF model, we show that the Probabilistic-Core problem is W[1]-hard for the parameter d, where d is the minimum degree of the core. We then design an FPT algorithm for the parameter treewidth.<\/jats:p>","DOI":"10.3390\/a13010003","type":"journal-article","created":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T09:50:33Z","timestamp":1576835433000},"page":"3","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Parameterized Optimization in Uncertain Graphs\u2014A Survey and Some Results"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8771-3921","authenticated-orcid":false,"given":"N. S.","family":"Narayanaswamy","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Madras (IIT Madras), Chennai 600036, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Vijayaragunathan","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Madras (IIT Madras), Chennai 600036, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,19]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0191-2615(95)00024-0","article-title":"Dual graph representation of transport networks","volume":"30","author":"Barra","year":"1996","journal-title":"Trans. Res. Part B Methodol."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Hua, M., and Pei, J. (2010, January 22\u201326). Probabilistic Path Queries in Road Networks: Traffic Uncertainty Aware Path Selection. Proceedings of the 13th International Conference on Extending Database Technology (EDBT \u201910), Lausanne, Switzerland.","DOI":"10.1145\/1739041.1739084"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1101\/gr.2203804","article-title":"Predicting protein complex membership using probabilistic network reliability","volume":"14","author":"Asthana","year":"2004","journal-title":"Genome Res."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Domingos, P., and Richardson, M. (2001, January 26\u201329). Mining the Network Value of Customers. Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201901), San Francisco, CA, USA.","DOI":"10.1145\/502512.502525"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1287\/opre.17.4.583","article-title":"Shortest Paths in Probabilistic Graphs","volume":"17","author":"Frank","year":"1969","journal-title":"Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","article-title":"The Complexity of Enumeration and Reliability Problems","volume":"8","author":"Valiant","year":"1979","journal-title":"SIAM J. Comput."},{"key":"ref_7","unstructured":"Hoffmann, M., Erlebach, T., Krizanc, D., Mihal\u00e1k, M., and Raman, R. (2008, January 21\u201323). Computing Minimum Spanning Trees with Uncertainty. Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France."},{"key":"ref_8","unstructured":"Focke, J., Megow, N., and Mei\u00dfner, J. (2017, January 21\u201323). Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), London, UK."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1109\/TCT.1965.1082452","article-title":"Probabilistic Flows Through a Communication Network","volume":"12","author":"Frank","year":"1965","journal-title":"IEEE Trans. Circuit Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1002\/net.3230060208","article-title":"Maximum flow in probabilistic graphs-the discrete case","volume":"6","author":"Evans","year":"1976","journal-title":"Networks"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hassin, R., Ravi, R., and Salman, F.S. (2009). Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links. Algorithms-ESA 2009, Proceedings of the 17th Annual European Symposium, Copenhagen, Denmark, 7\u20139 September 2009, Springer.","DOI":"10.1007\/978-3-642-04128-0_24"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10878-017-0121-5","article-title":"Multiple facility location on a network with linear reliability order of edges","volume":"34","author":"Hassin","year":"2017","journal-title":"J. Comb. Optim."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Narayanaswamy, N.S., Nasre, M., and Vijayaragunathan, R. (2018, January 6\u201310). Facility Location on Planar Graphs with Unreliable Links. Proceedings of the Computer Science-Theory and Applications-13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia.","DOI":"10.1007\/978-3-319-90530-3_23"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.M., and Tardos, \u00c9. (2003, January 24\u201327). Maximizing the spread of influence through a social network. Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA.","DOI":"10.1145\/956750.956769"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Bonchi, F., Gullo, F., Kaltenbrunner, A., and Volkovich, Y. (2014, January 24\u201327). Core decomposition of uncertain graphs. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201914), New York, NY, USA.","DOI":"10.1145\/2623330.2623655"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Peng, Y., Zhang, Y., Zhang, W., Lin, X., and Qin, L. (2018, January 16\u201319). Efficient Probabilistic K-Core Computation on Uncertain Graphs. Proceedings of the 34th IEEE International Conference on Data Engineering (ICDE), Paris, France.","DOI":"10.1109\/ICDE.2018.00110"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/net.3230130210","article-title":"Calculating bounds on reachability and connectedness in stochastic networks","volume":"13","author":"Ball","year":"1983","journal-title":"Networks"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Zou, Z., and Li, J. (2013, January 7\u201310). Structural-Context Similarities for Uncertain Graphs. Proceedings of the 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA.","DOI":"10.1109\/ICDM.2013.22"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1287\/trsc.17.1.48","article-title":"A Maximum Expected Covering Location Model: Formulation, Properties and Heuristic Solution","volume":"17","author":"Daskin","year":"1983","journal-title":"Transp. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1002\/net.3230100206","article-title":"Complexity of network reliability computations","volume":"10","author":"Ball","year":"1980","journal-title":"Networks"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0885-064X(85)90021-4","article-title":"Monte-Carlo algorithms for the planar multiterminal network reliability problem","volume":"1","author":"Karp","year":"1985","journal-title":"J. Complex."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/0212053","article-title":"The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected","volume":"12","author":"Provan","year":"1983","journal-title":"SIAM J. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/18M1201846","article-title":"A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability","volume":"48","author":"Guo","year":"2019","journal-title":"SIAM J. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Ghosh, J., Ngo, H.Q., Yoon, S., and Qiao, C. (2007, January 6\u201312). On a Routing Problem Within Probabilistic Graphs and its Application to Intermittently Connected Networks. Proceedings of the 26th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, INFOCOM, Anchorage, AK, USA.","DOI":"10.1109\/INFCOM.2007.201"},{"key":"ref_25","unstructured":"Rubino, G. (1999). Network Performance Modeling and Simulation, Gordon and Breach Science Publishers, Inc.. chapter Network Reliability Evaluation."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Swamynathan, G., Wilson, C., Boe, B., Almeroth, K.C., and Zhao, B.Y. (2008, January 17\u201322). Do social networks improve e-commerce?: a study on social marketplaces. Proceedings of the first Workshop on Online Social Networks (WOSN 2008), Seattle, WA, USA.","DOI":"10.1145\/1397735.1397737"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1111\/0081-1750.00098","article-title":"The Cohesiveness of Blocks In Social Networks: Node Connectivity and Conditional Density","volume":"31","author":"White","year":"2001","journal-title":"Soc. Methodol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0304-3975(91)90263-2","article-title":"Shortest paths without a map","volume":"84","author":"Papadimitriou","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","article-title":"The Budgeted Maximum Coverage Problem","volume":"70","author":"Khuller","year":"1999","journal-title":"Inf. Process. Lett."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1086\/209118","article-title":"Social Ties and Word-of-Mouth Referral Behavior","volume":"14","author":"Brown","year":"1987","journal-title":"J. Consum. Res."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Richardson, M., and Domingos, P.M. (2002, January 23\u201326). Mining knowledge-sharing sites for viral marketing. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, AB, Canada.","DOI":"10.1145\/775047.775057"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1287\/mnsc.15.5.215","article-title":"A New Product Growth for Model Consumer Durables","volume":"15","author":"Bass","year":"1969","journal-title":"Manag. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1080\/07408170500216480","article-title":"Facility location under uncertainty: A review","volume":"38","author":"Snyder","year":"2006","journal-title":"IIE Trans."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1002\/net.3230220303","article-title":"Location of facilities on a network subject to a single-edge failure","volume":"22","author":"Eiselt","year":"1992","journal-title":"Networks"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0304-3975(97)00124-2","article-title":"A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges","volume":"209","author":"Colbourn","year":"1998","journal-title":"Theor. Comput. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Ding, W. (2009, January 19\u201321). Computing the Most Reliable Source on Stochastic Ring Networks. Proceedings of the 2009 WRI World Congress on Software Engineering, Xiamen, China.","DOI":"10.1109\/WCSE.2009.31"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/j.tcs.2009.08.003","article-title":"A linear time algorithm for computing a most reliable source on a tree network with faulty nodes","volume":"412","author":"Ding","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1002\/(SICI)1097-0037(199605)27:3<219::AID-NET7>3.0.CO;2-L","article-title":"A single facility location problem on a tree with unreliable edges","volume":"27","author":"Melachrinoudis","year":"1996","journal-title":"Networks"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01588971","article-title":"An analysis of approximations for maximizing submodular set functions\u2014I","volume":"14","author":"Nemhauser","year":"1978","journal-title":"Math. Program."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1122","DOI":"10.1287\/opre.28.5.1122","article-title":"The Stochastic Shortest Route Problem","volume":"28","author":"Sigal","year":"1980","journal-title":"Oper. Res."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1109\/90.779203","article-title":"QoS routing in networks with inaccurate information: Theory and algorithms","volume":"7","author":"Guerin","year":"1999","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_43","unstructured":"G\u00fcnne\u00e7, D., and Salman, F.S. (2007, January 22\u201325). Assessing the reliability and the expected performance of a network under disaster risk. Proceedings of the International Network Optimization Conference (INOC), Spa, Belgium."},{"key":"ref_44","unstructured":"Diestel, R. (2012). Graph Theory, Springer. [4th ed.]. Graduate Texts in Mathematics."},{"key":"ref_45","first-page":"1","article-title":"A Tourist Guide through Treewidth","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybern."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Kloks, T. (1994). Treewidth, Computations and Approximations, Springer. Lecture Notes in Computer Science.","DOI":"10.1007\/BFb0045375"},{"key":"ref_47","unstructured":"Downey, R.G., and Fellows, M.R. (1992, January 22\u201325). Fixed-parameter intractability. Proceedings of the Seventh Annual Structure in Complexity Theory Conference, Boston, MA, USA."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Koster, A.M.C.A., Wolle, T., and Bodlaender, H.L. (2005, January 10\u201313). Degree-Based Treewidth Lower Bounds. Proceedings of the 4th International Workshop, WEA 2005 Experimental and Efficient Algorithms, Santorini Island, Greece.","DOI":"10.1007\/11427186_11"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/3\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:43:46Z","timestamp":1760190226000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,19]]},"references-count":48,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["a13010003"],"URL":"https:\/\/doi.org\/10.3390\/a13010003","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,19]]}}}