Document Open Access Logo

Parameterized Complexity of Multi-Node Hubs

Authors Saket Saurabh, Meirav Zehavi

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.8.pdf
  • Filesize: 487 kB
  • 14 pages

Document Identifiers

Author Details

Saket Saurabh
  • University of Bergen, Norway, and Institute of Mathematical Science, HBNI, India
Meirav Zehavi
  • Ben-Gurion University, Israel

Cite As Get BibTex

Saket Saurabh and Meirav Zehavi. Parameterized Complexity of Multi-Node Hubs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.8

Abstract

Hubs are high-degree nodes within a network. The examination of the emergence and centrality of hubs lies at the heart of many studies of complex networks such as telecommunication networks, biological networks, social networks and semantic networks. Furthermore, identifying and allocating hubs are routine tasks in applications. In this paper, we do not seek a hub that is a single node, but a hub that consists of k nodes. Formally, given a graph G=(V,E), we a seek a set A subseteq V of size k that induces a connected subgraph from which at least p edges emanate. Thus, we identify k nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call Multi-Node Hub (MNH), can also be viewed as a variant of the classic Max Cut problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter k, our main contribution is the first parameterized algorithm that shows that MNH is FPT with respect to the parameter p.
Despite recent breakthrough advances for cut-problems like Multicut and Minimum Bisection, MNH is still very challenging. Not only does a connectivity constraint has to be handled on top of the involved machinery developed for these problems, but also the fact that MNH is a maximization problem seems to prevent the applicability of this machinery in the first place. To deal with the latter issue, we give non-trivial reduction rules that show how MNH can be preprocessed into a problem where it is necessary to delete a bounded-in-parameter number of vertices. Then, to handle the connectivity constraint, we use a novel application of the form of tree decomposition introduced by Cygan et al. [STOC 2014] to solve Minimum Bisection, where we demonstrate how connectivity constraints can be replaced by simpler size constraints. Our approach may be relevant to the design of algorithms for other cut-problems of this nature.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • hub
  • bisection
  • tree decomposition

Metrics

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

References

  1. L A Adamic, R M Lukose, A R Puniyani, and B A Huberman. Search in power-law networks. CoRR cs.NI/0103016, 2001. Google Scholar
  2. A A Ageev and M Sviridenko. Approximation algorithms formaximum coverage andmax cutwith given sizes of parts. In IPCO, pages 17-30, 1999. Google Scholar
  3. N Alon, R Yuster, and U Zwick. Color coding. J. ACM, 42(4):844-856, 1995. Google Scholar
  4. D Balcan, H Hu, B Goncalves, P Bajardi, C Poletto, J J Ramasco, D Paolotti, N Perra, M Tizzoni, W Van den Broeck, V Colizza, and A Vespignani. Seasonal transmission potential and activity peaks of the new influenza A(H1N1): a Monte Carlo likelihood analysis based on human mobility. BMC Medicine, 7(45):29, 2009. Google Scholar
  5. A Barabasi and R Albert. Emergence of scaling in random networks. Science, 286:509, 1999. Google Scholar
  6. M Berlingerio, M Coscia, F Giannotti, A Monreale, and D Pedreschi. The pursuit of hubbiness: Analysis of hubs in large multidimensional networks. J. Comput. Science, 2:223-237, 2011. Google Scholar
  7. D Binkele-Raible. Amortized analysis of exponential time and parameterized algorithms: Measure and conquer and reference search trees. PhD Thesis, University of Trier, 2009. Google Scholar
  8. E Bonnet, B Escoffier, V T Paschos, and E Tourniaire. Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization. Algorithmica, 71(3):566-580, 2015. Google Scholar
  9. L Cai. Parameter complexity of cardinality constrained optimization problems. Comput. J., 51(1):102-121, 2008. Google Scholar
  10. R H Chitnis, M Cygan, M T Hajiaghayi, M Pilipczuk, and M Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In FOCS, pages 460-469, 2012. Google Scholar
  11. R H Chitnis, M Cygan, M T Hajiaghayi, M Pilipczuk, and M Pilipczuk. Designing FPT algorithms for cut problems using randomized contractions. In http://arxiv.org/pdf/1207.4079v1.pdf, 2012. Google Scholar
  12. R Crowston, G Gutin, M Jones, and G Muciaccia. Maximum balanced subgraph problem parameterized above lower bound. Theor. Comput. Sci., 513:53-64, 2013. Google Scholar
  13. R Crowston, M Jones, and M Mnich. Max-Cut Parameterized Above the Edwards-Erdős Bound. Algorithmica, 72(3):734-757, 2015. Google Scholar
  14. M Cygan. Deterministic parameterized connected vertex cover. In SWAT, pages 95-106, 2012. Google Scholar
  15. M Cygan, D Lokshtanov, M Pilipczuk, M Pilipczuk, and S Saurabh. Minimum bisection is fixed parameter tractable. In STOC, pages 323-332, 2014. Google Scholar
  16. M Cygan, J Nederlof, M Pilipczuk, M Pilipczuk, J M M van Rooij, and J O Wojtaszczyk. Deterministic parameterized connected vertex cover. In FOCS, pages 150-159, 2012. Google Scholar
  17. U Feige and M Langberg. Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms, 41(2):174-211, 2001. Google Scholar
  18. H Fernau and D Manlove. Vertex and edge covers with clustering properties: Complexity and algorithms. J. Discrete Algorithms, 7(2):149-167, 2009. Google Scholar
  19. D W Franks, J Noble, P Kaufmann, and S Stagl. Extremism propagation in social networks with hubs. Adaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems, 16:264-274, 2008. Google Scholar
  20. M X Goemans and D P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115-1145, 1995. Google Scholar
  21. P Goymer. Network biology: Why do we need hubs? Nature Reviews Genetics, 9:650-651, 2008. Google Scholar
  22. J Guo, R Niedermeier, and S Wernicke. Parameterized complexity of generalized vertex cover problems. In WADS, pages 36-48, 2005. Google Scholar
  23. M T Hajiaghayi, G Kortsarz, R MacDavid, M Purohit, and K K Sarpatwar. Approximation algorithms for connected maximum cut and telated problems. In ESA, pages 693-704, 2015. Google Scholar
  24. X He and J Zhang. Why Do Hubs Tend to Be Essential in Protein Networks? PLOS Genetics, 2(6):e88, 2006. Google Scholar
  25. H Jeong, B Tombor, R Albert, Z N Oltvai, and A L Barabasi. The large-scale organization of metabolic networks. Nature, 407:651-654, 2000. Google Scholar
  26. S Khot, G Kindler, E Mossel, and R O'Donnell. Optimization, approximation, and complexity classes. SICOMP, 37(1):319-357, 2007. Google Scholar
  27. J M Kleinberg. Authoritative sources in a hyperlinked environment. J. ACM, 46:604-632, 1999. Google Scholar
  28. J Kneis, A Langer, and P Rossmanith. A new algorithm for finding trees with many leaves. Algorithmica, 61:882-897, 2011. Google Scholar
  29. J Lee, V Nagarajan, and X Shen. Max-Cut Under Graph Constraints. In IPCO, pages 50-62, 2016. Google Scholar
  30. J Leskovec, L A Adamic, and Huberman B A. The dynamics of viral marketing. In EC, pages 228-237, 2006. Google Scholar
  31. D Lokshtanov, M S Ramanujan, S Saurabh, and M Zehavi. Reducing CMSO Model Checking to Highly Connected Graphs. In ICALP, pages 135:1-135:14, 2018. Google Scholar
  32. D Lokshtanov, S Saurabh, R Sharma, and M Zehavi. Balanced Judicious Bipartition is Fixed-Parameter Tractable. In FSTTCS, pages 40:40-40:15, 2017. Google Scholar
  33. X Lu, V J Vipul, P W Finn, and D L Perkins. Hubs in biological interaction networks exhibit low changes in expression in experimental asthma. Molecular Systems Biology, 3(98), 2008. Google Scholar
  34. M Mahajan and V Raman. Parameterizing above Guaranteed Values: MaxSat and MaxCut. J. Algorithms, 31(2):335-354, 1999. Google Scholar
  35. A S Maiya and T Y Berger-Wolf. Online sampling of high centrality individuals in social networks. In PAKDD, pages 91-98, 2010. Google Scholar
  36. D Molle, S Richter, and P Rossmanith. Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Theory Comput. Syst., 43(2):234-253, 2008. Google Scholar
  37. C H Papadimitriou and M Yannakakis. Optimization, approximation, and complexity classes. J. Comput. Syst. Sci., 43(3):425-440, 1991. Google Scholar
  38. V Raman and S Saurabh. Improved fixed parameter tractable algorithms for two "edge" problems: MAXCUT and MAXDAG. Inf. Process. Lett., 104(2):65-72, 2007. Google Scholar
  39. S Saurabh and M Zehavi. (k,n-k)-Max-Cut: an O^*(2^p)-time algorithm and a polynomial kernel. In LATIN, pages 686-699, 2016. Google Scholar
  40. H Shachnai and M Zehavi. Parameterized algorithms for graph partitioning problems. In WG, pages 384-395, 2014. Google Scholar
  41. X Shi, B Tseng, and L Adamic. Looking at the Blogosphere Topology through Different Lenses. In ICWSM, 2007. Google Scholar
  42. S Vicente, V Kolmogorov, and C Rother. Graph cut based image segmentation with connectivity priors. In CVPR, pages 1-8, 2008. Google Scholar
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 About DROPS Imprint Privacy Contact