Getting linear time in graphs of bounded neighborhood diversity. (English) Zbl 07907337
Summary: Parameterized complexity, introduced to efficiently solve NP-hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity (nd) for several graph theoretic problems in \( P \): Maximum \( b \)-Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular-width (mw) and consequently – as nd is a special case of mw – by nd. However, the proposed novel algorithms allow for improving the computational complexity from time \( O\left(f\left(\mathsf{mw}\right)\cdotp n+m\right) \) – where \( n \) and \( m \) denote, respectively, the number of vertices and edges in the input graph – to time \( O\left(g\left(\mathsf{nd}\right)+n+m\right) \) which is only additive in the size of the input. Then we consider some classical NP-hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small – nonnecessarily constant – values of the neighborhood diversity parameter.
© 2024 Wiley Periodicals LLC
© 2024 Wiley Periodicals LLC
MSC:
| 68-XX | Computer science |
References:
| [1] | A.Abboud and V. V.Williams, “Popular conjectures imply strong lower bounds for dynamic problems,” Proceedings of the IEEE symposium on foundations of computer science (FOCS’14), IEEE, Washington, 2014, pp. 434-443. |
| [2] | A.Abboud, F.Grandoni, and V.Vassilevska Williams, Subcubic equivalences between graph centrality problems, APSP, and diameter, ACM Trans. Algor.19 (2023), no. 1, 1-30. · Zbl 07753154 |
| [3] | F. N.Abu‐Khzam, S.Li, C.Markarian, F.Meyer auf der Heide, and P.Podlipyan, “Modular‐width: An auxiliary parameter for parameterized parallel complexity,” Frontiers in Algorithmics, (FAW’17), LNCS, Vol 10336, M.Xiao (ed.) and F.Rosamond (ed.) (eds.), Springer, Heidelberg, 2017. · Zbl 1429.68326 |
| [4] | N.Alon, R.Yuster, and U.Zwick, Finding and counting given length cycles, Algorithmica17 (1997), no. 3, 209-223. · Zbl 0865.68093 |
| [5] | S.Arnborg, D. G.Corneil, and A.Proskurowski, Complexity of finding embeddings in a k‐tree, SIAM J Algebr Discret. Methods8(2) (1987), 277-284. · Zbl 0611.05022 |
| [6] | L.Becchetti, P.Boldi, C.Castillo, and A.Gionis, Efficient algorithms for large‐scale local triangle counting, ACM Trans Knowl Discov Data4 (2010), no. 3, 1-28. |
| [7] | R.Belmonte, F. V.Fomin, P. A.Golovach, and M. S.Ramanujan, Metric dimension of bounded tree‐length graphs, SIAM J. Discret. Math.31 (2017), no. 2, 1217-1243. · Zbl 1371.68103 |
| [8] | M.Bentert, T.Fluschnik, A.Nichterlein, and R.Niedermeier, Parameterized aspects of triangle enumeration, J. Comput. Syst. Sci.103 (2019), 61-77. · Zbl 1430.68176 |
| [9] | M.Borassi, P.Crescenzi, and M.Habib, Into the square: On the complexity of some quadratic‐time solvable problems, Electron. Notes Theor. Comput. Sci.322 (2016), 51-67. · Zbl 1345.68170 |
| [10] | M.Chudnovsky, G.Cornuejols, X.Liu, P.Seymour, and K.Vuskovic, Recognizing Berge graphs, Combinatorica25 (2005), 143-186. · Zbl 1089.05027 |
| [11] | M.Chudnovsky, N.Robertson, P.Seymour, and R.Thomas, The strong perfect graph theorem, Ann. Math.164 (2006), no. 1, 51-229. · Zbl 1112.05042 |
| [12] | G.Cordasco, L.Gargano, A. A.Rescigno, and U.Vaccaro, Evangelism in social networks: algorithms and complexity, Networks71 (2018), no. 4, 346-357. · Zbl 1396.91606 |
| [13] | G.Cordasco, L.Gargano, and A. A.Rescigno, “Speeding up networks mining via Neighborhood diversity,” The tenth international conference on fun with algorithms (FUN 2020), Dagstuhl Publishing, Wadern, 2021. · Zbl 1515.68234 |
| [14] | G.Cordasco, L.Gargano, and A. A.Rescigno, Parameterized complexity for iterated type partitions and modular‐width, Discret. Appl. Math.350 (2024), 100-122. · Zbl 07829715 |
| [15] | T. H.Cormen, C. E.Leiserson, R. L.Rivest, and C.Stein, Introduction to algorithms, 3rd ed., MIT Press, Cambridge, 2009. · Zbl 1187.68679 |
| [16] | D.Corneil, H.Lerchs, and L.Burlingham, Complement reducible graphs, Discret. Appl. Math.3 (1981), 163-174. · Zbl 0463.05057 |
| [17] | G.Cornuejols, X.Liu, and K.Vuskovic, “A polynomial algorithm for recognizing perfect graphs,” Proceedings of 44th annual IEEE symposium on foundations of computer science, IEEE, Washington, 2003, pp. 20-27. |
| [18] | D.Coudert, G.Ducoffe, and A.Popa, P‐FPT algorithms for bounded clique‐width graphs, ACM Trans. Algor.15 (2019), no. 3, 33:1-33:57. · Zbl 1454.68098 |
| [19] | K.Dabrowski, V.Lozin, H.Müller, and D.Rautenbach, “Parameterized algorithms for the independent set problem in some hereditary graph classes,” Combinatorial algorithms. IWOCA 2010, LNCS, Vol 6460, Springer, Heidelberg, 2011. · Zbl 1295.68131 |
| [20] | M.Doucha and J.Kratochvíl, “Cluster vertex deletion: A parameterization between vertex cover and clique‐width,” Mathematical Foundations of Computer Science, Vol 2012, Springer, Heidelberg, 2012, pp. 348-359. · Zbl 1365.68278 |
| [21] | R. G.Downey and M. R.Fellows, Parameterized complexity, Springer, New York, 2012. |
| [22] | G.Ducoffe, Maximum matching in almost linear time on graphs of bounded clique‐width, Algorithmica84 (2022), 3489-3520. · Zbl 07608297 |
| [23] | G.Ducoffe and A.Popa, The use of a pruned modular decomposition for maximum matching algorithms on some graph classes, Discret. Appl. Math.291 (2021a), 201-222. · Zbl 1509.68198 |
| [24] | G.Ducoffe and A.Popa, The b‐matching problem in distance‐hereditary graphs and beyond, Discret. Appl. Math.305 (2021b), 233-246. · Zbl 1476.05166 |
| [25] | P.Dvorák, D.Knop, and T.Toufar, Target set selection in dense graph classes, SIAM J. Discret. Math.36 (2022), no. 1, 536-572. · Zbl 1542.68142 |
| [26] | J.Edmonds, Paths, trees, and flowers, Can. J. Math.17 (1965), no. 3, 449-467. · Zbl 0132.20903 |
| [27] | Y.Faenza, G.Oriolo, and G.Stauffer, Solving the weighted stable set problem in claw‐free graphs via decomposition, J. ACM61 (2014), no. 4, 1-41. · Zbl 1321.05260 |
| [28] | M.Farber, Independent domination in chordal graphs, Oper. Res. Lett.1 (1982), 134-138. · Zbl 0495.05053 |
| [29] | J.Fiala, T.Gavenciak, D.Knop, M.Koutecky, and J.Kratochvíl, Parameterized complexity of distance labeling and uniform channel assignment problems, Discret. Appl. Math.248 (2018), 46-55. · Zbl 1395.05143 |
| [30] | F. V.Fomin, M.Liedloff, P.Montealegre, and I.Todinca, “Algorithms parameterized by vertex cover and modular width, through potential maximal cliques,” Algorithm theory - SWAT 2014, LNCS, Vol 8503, R.Ravi (ed.) and I. L.Gørtz (ed.) (eds.), Springer, Heidelberg, 2014. · Zbl 1386.68068 |
| [31] | H. N.Gabow, Data structures for weighted matching and extensions to [( b \]\)‐matching and [( f \]\)‐factors, ACM Trans. Algor.14 (2018), no. 3, 39. · Zbl 1454.68030 |
| [32] | J.Gajarský, M.Lampis, and S.Ordyniak, “Parameterized algorithms for modular‐width,” Parameterized and exact computation. IPEC 2013, LNCS, Vol 8246, G.Gutin (ed.) and S.Szeider (ed.) (eds.), Springer, Heidelberg, 2013. · Zbl 1406.68080 |
| [33] | T.Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar.18 (1967), 26-66. · Zbl 0153.26002 |
| [34] | R.Ganian. Using neighborhood diversity to solve hard problems. arXiv:1201.3091 2012. |
| [35] | M. R.Garey and D. S.Johnson, Computers and intractability a guide to the theory of NP‐completeness, Freeman, San Francisco, 1979. · Zbl 0411.68039 |
| [36] | L.Gargano and A. A.Rescigno, Complexity of conflict‐free colorings of graphs, Theor. Comput. Sci.566 (2015), 39-49. · Zbl 1317.68071 |
| [37] | A. C.Giannopoulou, G. B.Mertzios, and R.Niedermeier, Polynomial fixed‐parameter algorithms: a case study for longest path on interval graphs, Theor. Comput. Sci.689 (2017), 67-95. · Zbl 1372.68124 |
| [38] | M.Grötschel, L.Lovász, and A.Schrijver, Polynomial algorithm for perfect graphs, Ann. Discret. Math.21 (1984), 325-356. · Zbl 0554.05041 |
| [39] | J.Hao and J. B.Orlin, A faster algorithm for finding the minimum cut in a directed graph, J. Algor.17 (1994), no. 3, 424-446. · Zbl 0819.68087 |
| [40] | W. L.Hsu and G. L.Nemhauser, Algorithms for maximum weight cliques, minimum weighted clique covers and cardinality colorings of claw‐free perfect graphs, Ann. Discret. Math.21 (1984), 317-329. |
| [41] | R.Impagliazzo and R.Paturi, On the complexity of k‐SAT, J. Comput. Syst. Sci.62 (2001), no. 2, 367-375. · Zbl 0990.68079 |
| [42] | A.Itai and M.Rodeh, Finding a minimum circuit in a graph, SIAM J. Comput.7 (1978), no. 4, 413-423. · Zbl 0386.68064 |
| [43] | M. N.Kolountzakis, G. L.Miller, R.Peng, and C. E.Tsourakakis, Efficient triangle counting in large graphs via degree‐based vertex partitioning, Internet Math.8 (2012), no. 1-2, 161-185. · Zbl 1245.05120 |
| [44] | S.Kratsch and F.Nelles, “Efficient and adaptive parameterized algorithms on modular decompositions,” Proceeding of 26th annual European symposium on algorithms (ESA 2018), Vol 112, Leibniz International Proceedings in Informatics (LIPIcs), Germany, 2018, pp. 55:1-55:15. · Zbl 1524.68235 |
| [45] | S.Kratsch, F.Nelles, and A.Simon. On triangle counting parameterized by twin‐width. arXiv:2202.06708 2022. |
| [46] | M.Lampis, Algorithmic meta‐theorems for restrictions of treewidth, Algorithmica64 (2012), 19-37. · Zbl 1252.68154 |
| [47] | M.Latapy, Main‐memory triangle computations for very large (sparse (power‐law)) graphs, Theor. Comput. Sci.407 (2008), no. 1-3, 458-473. · Zbl 1152.68045 |
| [48] | D.Lokshtanov, M.Vatshelle, and Y.Villanger, “Independent set in P5‐free graphs in polynomial time,” Proceedings of the twenty‐fifth annual ACM‐SIAM symposium on discrete algorithms, (SODA’14), SIAM, Philadelphia, 2014, pp. 570-581. · Zbl 1422.68126 |
| [49] | D.Malyshev, A complexity dichotomy and a new boundary class for the dominating set problem, J. Comb. Optim.32 (2016), 226-243. · Zbl 1354.90111 |
| [50] | G. B.Mertzios, A.Nichterlein, and R.Niedermeier, “The power of linear‐time data reduction for maximum matching,” Proceedings of international symposium on mathematical foundations of computer science (MFCS’17), Vol 83, Dagstuhl Publishing, Wadern, 2017, pp. 46:1-46:14. · Zbl 1441.68192 |
| [51] | S.Micali and V. V.Vazirani, “An [( o\left(\operatorname{} sqrt\left(|V|\right)|E|\right) \]\) algorithm for finding maximum matching in general graphs,” 21st annual symposium on foundations of computer science, DBLP, New York, 1980, pp. 17-27. |
| [52] | M. E. J.Newman, The structure and function of complex networks, SIAM Rev.45 (2003), no. 2, 167-256. · Zbl 1029.68010 |
| [53] | R.Niedermeier, Invitation to fixed‐parameter algorithms, Oxford University Press, Oxford, 2006. · Zbl 1095.68038 |
| [54] | S.Oum, Approximating rank‐width and clique‐width, ACM. Algor.5 (2008), no. 10, 1-20. · Zbl 1451.05231 |
| [55] | S.Poljak, A note on stable sets and coloring of graphs, Comment. Math. Univ. Carol.15 (1974), 307-309. · Zbl 0284.05105 |
| [56] | M.Tedder, D.Corneil, M.Habib, and C.Paul, “Simpler linear‐time modular decomposition via recursive factorizing permutations,” Proceedings of international colloquium on automata, languages and programming (ICALP’08), LNCS, Springer, Heidelberg, 5125, 2008. · Zbl 1153.68410 |
| [57] | V.Vassilevska Williams, “Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk),” International symposium on parameterized and exact computation (IPEC), Vol 43, LIPICS, Germany, 2015, pp. 16-28. |
| [58] | V.Vassilevska Williams and R. R.Williams, “Subcubic equivalences between path, matrix and triangle problems,” IEEE symposium on foundations of computer science (FOCS), IEEE, New York, 2010, pp. 645-654. |
| [59] | V.Vassilevska Williams, Y.Xu, Z.Xu, and R.Zhou. New bounds for matrix multiplication: from alpha to omega. arXiv:2307.07970 2023. |
| [60] | M.Yannakakis and F.Gavril, Edge dominating sets in graphs, SIAM J. Appl. Math.38 (1980), no. 3, 364-372. · Zbl 0455.05047 |
| [61] | Y.Zhang and S.Parthasarathy, “Extracting analyzing and visualizing triangle k‐core motifs within networks,” Proceedings of 28th International conference on data engineering, (ICDE’12), IEEE, New York, 2012, pp. 1049-1060. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
