Document Open Access Logo

Budgeted Dominating Sets in Uncertain Graphs

Authors Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy , David Peleg , R. Vijayaragunathan

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.32.pdf
  • Filesize: 0.93 MB
  • 22 pages

Document Identifiers

Author Details

Keerti Choudhary
  • Indian Institute of Technology Delhi, India
Avi Cohen
  • Tel Aviv University, Israel
N. S. Narayanaswamy
  • Department of Computer Science and Engineering, IIT Madras, India
David Peleg
  • Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel
R. Vijayaragunathan
  • Department of Computer Science and Engineering, IIT Madras, India

Acknowledgements

We thank an anonymous reviewer for pointing us to [S. Arnborg et al., 1991], yielding a shorter proof of the FPT algorithm for Uni-PBDS parameterized by treewidth and k. David Peleg is supported by the Venky Harinarayanan and Anand Rajaraman Visiting Chair Professorship at the Indian Institute of Technology Madras, Chennai, India ( IIT Madras). Supported by the chair’s funds, this work was done in part when David Peleg, Avi Cohen, and Keerti Choudhary visited IIT Madras and when R. Vijayaragunathan visited the Weizmann Institute of Science, Rehovot, Israel.

Cite AsGet BibTex

Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan. Budgeted Dominating Sets in Uncertain Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.MFCS.2021.32

Abstract

We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Uncertain graphs
  • Dominating set
  • NP-hard
  • PTAS
  • treewidth
  • planar graph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. A. Abboud and K. Lewi. Exact weight subgraphs and the k-sum conjecture. In Proc. 40th Int. Colloq. on Automata, Languages, and Programming (ICALP), pages 1-12. Springer, 2013. Google Scholar
  2. A. Abboud, K. Lewi, and R. Williams. Losing weight by gaining edges. In Proc. 22th European Symp. on Algorithms (ESA), pages 1-12. Springer, 2014. Google Scholar
  3. J. Alber, M. R. Fellows, and R. Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363-384, 2004. Google Scholar
  4. J. Alber, H. Fernau, and R. Niedermeier. Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms, 52(1):26-56, 2004. URL: https://doi.org/10.1016/j.jalgor.2004.03.005.
  5. T.M. Apostol. Calculus. Number v. 1 in Blaisdell book in pure and applied mathematics. Blaisdell Pub. Co., 1969. Google Scholar
  6. S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12:308-340, 1991. Google Scholar
  7. S. Asthana, O. D. King, F. D. Gibbons, and F. P. Roth. Predicting protein complex membership using probabilistic network reliability. Genome Research, 14 6:1170-5, 2004. Google Scholar
  8. J. Añez, T. De La Barra, and B. Pérez. Dual graph representation of transport networks. Transportation Research Part B: Methodological, 30(3):209-216, 1996. URL: https://doi.org/10.1016/0191-2615(95)00024-0.
  9. M. O. Ball. Complexity of network reliability computations. Networks, 10(2):153-165, 1980. URL: https://doi.org/10.1002/net.3230100206.
  10. M. O. Ball and J. S. Provan. Calculating bounds on reachability and connectedness in stochastic networks. Networks, 13(2):253-278, 1983. URL: https://doi.org/10.1002/net.3230130210.
  11. F. Bonchi, F. Gullo, A. Kaltenbrunner, and Y. Volkovich. Core decomposition of uncertain graphs. In Proc. 20th ACM Int. Conf. on Knowledge Discovery and Data Mining (KDD), pages 1316-1325, 2014. Google Scholar
  12. C. J. Colbourn and G. Xue. A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges. Theoretical Computer Science, 209(1):331-345, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00124-2.
  13. B. Courcelle. The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput., 85(1):12-75, 1990. Google Scholar
  14. B. Courcelle and J. Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encycl. Mathematics and Its Applications. Cambridge Univ. Press, 2012. Google Scholar
  15. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  16. M. S. Daskin. A maximum expected covering location model: Formulation, properties and heuristic solution. Transportation Science, 17(1):48-70, 1983. URL: http://EconPapers.repec.org/RePEc:inm:ortrsc:v:17:y:1983:i:1:p:48-70.
  17. Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  18. Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012. Google Scholar
  19. W. Ding. Computing the most reliable source on stochastic ring networks. In 2009 WRI World Congress on Software Engineering, volume 1, pages 345-347, May 2009. URL: https://doi.org/10.1109/WCSE.2009.31.
  20. W. Ding. Extended most reliable source on an unreliable general network. In 2011 International Conference on Internet Computing and Information Services, pages 529-533, September 2011. URL: https://doi.org/10.1109/ICICIS.2011.138.
  21. W. Ding and G. Xue. A linear time algorithm for computing a most reliable source on a tree network with faulty nodes. Theoretical Computer Science, 412(3):225-232, 2011. Combinatorial Optimization and Applications. URL: https://doi.org/10.1016/j.tcs.2009.08.003.
  22. Pedro Domingos and Matt Richardson. Mining the network value of customers. In Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '01, pages 57-66, New York, NY, USA, 2001. ACM. URL: https://doi.org/10.1145/502512.502525.
  23. Rodney G. Downey and Michael R. Fellows. Fixed parameter tractability and completeness. In Complexity Theory: Current Research, Dagstuhl Workshop, February 2-8, 1992, pages 191-225, 1992. Google Scholar
  24. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  25. P. G. Drange, M. S. Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. S. Villaamil, S. Saurabh, S. Siebertz, and S. Sikdar. Kernelization and sparseness: the case of dominating set. In Proc. 33rd Symp. on Theoretical Aspects of Computer Science (STACS), pages 31:1-31:14, 2016. Google Scholar
  26. T. Erlebach, M. Hoffmann, D. Krizanc, M. Mihalák, and R. Raman. Computing minimum spanning trees with uncertainty. In STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings, pages 277-288, 2008. URL: https://doi.org/10.4230/LIPIcs.STACS.2008.1358.
  27. J. R. Evans. Maximum flow in probabilistic graphs-the discrete case. Networks, 6(2):161-183, 1976. URL: https://doi.org/10.1002/net.3230060208.
  28. Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Subexponential algorithms for partial cover problems. Inf. Process. Lett., 111(16):814-818, 2011. URL: https://doi.org/10.1016/j.ipl.2011.05.016.
  29. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Bidimensionality and kernels. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 503-510. SIAM, 2010. Google Scholar
  30. Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Kernels for (connected) dominating set on graphs with excluded topological minors. ACM Trans. Algorithms, 14(1):6:1-6:31, 2018. URL: https://doi.org/10.1145/3155298.
  31. H. Frank and S. Hakimi. Probabilistic flows through a communication network. IEEE Transactions on Circuit Theory, 12(3):413-414, September 1965. URL: https://doi.org/10.1109/TCT.1965.1082452.
  32. M. Frick and M. Grohe. Deciding first-order properties of locally tree-decomposalbe graphs. In Proc. 26th Int. Colloq. on Automata, Languages and Programming (ICALP), pages 331-340, 1999. Google Scholar
  33. Heng Guo and Mark Jerrum. A polynomial-time approximation algorithm for all-terminal network reliability. SIAM J. Comput., 48(3):964-978, 2019. URL: https://doi.org/10.1137/18M1201846.
  34. R. Hassin, R. Ravi, and F. S. Salman. Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links, pages 275-276. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. Google Scholar
  35. R. Hassin, R. Ravi, and F. S. Salman. Multiple facility location on a network with linear reliability order of edges. Journal of Combinatorial Optimization, pages 1-25, 2017. Google Scholar
  36. Dorit S. Hochbaum, editor. Approximation Algorithms for NP-hard Problems. PWS Publishing Co., Boston, MA, USA, 1997. Google Scholar
  37. M. Hua and J. Pei. Probabilistic path queries in road networks: Traffic uncertainty aware path selection. In Proc. 13th ACM Conf. on Extending Database Technology (EDBT), pages 347-358, 2010. Google Scholar
  38. R. M. Karp and M. Luby. Monte-carlo algorithms for the planar multiterminal network reliability problem. J. Complexity, 1(1):45-64, 1985. URL: https://doi.org/10.1016/0885-064X(85)90021-4.
  39. D. Kempe, J. M. Kleinberg, and E. Tardos. Maximizing the spread of influence through a social network. In Proc. Ninth ACM Conf. on Knowledge Discovery and Data Mining (KDD), pages 137-146, 2003. Google Scholar
  40. Samir Khuller, Anna Moss, and Joseph Naor. The budgeted maximum coverage problem. Inf. Process. Lett., 70(1):39-45, 1999. URL: https://doi.org/10.1016/S0020-0190(99)00031-9.
  41. T. Kloks. Treewidth, Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994. Google Scholar
  42. J. Kneis, D. Mölle, and P. Rossmanith. Partial vs. complete domination: T-dominating set. In Proc. 33rd Conf. on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 367-376. Springer-Verlag, 2007. Google Scholar
  43. Emanuel Melachrinoudis and Mary E. Helander. A single facility location problem on a tree with unreliable edges. Networks, 27(4):219-237, 1996. URL: https://doi.org/10.1002/(SICI)1097-0037(199605)27:3.
  44. N. S. Narayanaswamy, M. Nasre, and R. Vijayaragunathan. Facility location on planar graphs with unreliable links. In Proc. 13th Computer Science Symp in Russia (CSR), pages 269-281, 2018. Google Scholar
  45. N. S. Narayanaswamy and R. Vijayaragunathan. Parameterized optimization in uncertain graphs - A survey and some results. Algorithms, 13(1):3, 2020. Google Scholar
  46. G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions - i. Mathematical Programming, 14(1):265-294, 1978. URL: https://doi.org/10.1007/BF01588971.
  47. M. Patrascu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd ACM Symp. on Theory of Computing (STOC), pages 603-610, 2010. Google Scholar
  48. M. Patrascu and R. Williams. On the possibility of faster SAT algorithms. In Proc. 21st ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1065-1075, 2010. Google Scholar
  49. Y. Peng, Y. Zhang, W. Zhang, X. Lin, and L. Qin. Efficient probabilistic k-core computation on uncertain graphs. In Proc. 34th IEEE Conf. on Data Engineering (ICDE), pages 1192-1203, 2018. Google Scholar
  50. Geevarghese Philip, Venkatesh Raman, and Somnath Sikdar. Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms, 9(1):11, 2012. URL: https://doi.org/10.1145/2390176.2390187.
  51. J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput., 12(4):777-788, 1983. URL: https://doi.org/10.1137/0212053.
  52. G. Swamynathan, C. Wilson, B. Boe, K. C. Almeroth, and B. Y. Zhao. Do social networks improve e-commerce?: a study on social marketplaces. In Proc. 1st Workshop on Online Social Networks (WOSN), pages 1-6, 2008. Google Scholar
  53. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. URL: https://doi.org/10.1137/0208032.
  54. Douglas R. White and Frank Harary. The cohesiveness of blocks in social networks: Node connectivity and conditional density. Sociological Methodology, 31(1):305-359, 2001. URL: https://doi.org/10.1111/0081-1750.00098.
  55. Zhaonian Zou and Jianzhong Li. Structural-context similarities for uncertain graphs. In 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA, December 7-10, 2013, pages 1325-1330, 2013. URL: https://doi.org/10.1109/ICDM.2013.22.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact