{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:13:58Z","timestamp":1758845638943,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T00:00:00Z","timestamp":1569628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T00:00:00Z","timestamp":1569628800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["340506"],"award-info":[{"award-number":["340506"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n<jats:p>We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions\/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of <jats:italic>O<\/jats:italic>(1) with high probability. This algorithm requires the assumption of an <jats:italic>oblivious adversary<\/jats:italic>, meaning that the future sequence of edge insertions\/deletions in the graph cannot depend in any way on the algorithm\u2019s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in <jats:italic>O<\/jats:italic>(1) update time. In this paper, we resolve this question. We present a new <jats:italic>deterministic<\/jats:italic> fully dynamic algorithm that maintains a <jats:italic>O<\/jats:italic>(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of <jats:italic>O<\/jats:italic>(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of <jats:inline-formula><jats:alternatives><jats:tex-math>$$(2+\\varepsilon )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mo>(<\/mml:mo><mml:mn>2<\/mml:mn><mml:mo>+<\/mml:mo><mml:mi>\u03b5<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> and an amortized update time of <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\log n\/\\varepsilon ^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mo>log<\/mml:mo><mml:mi>n<\/mml:mi><mml:mo>\/<\/mml:mo><mml:msup><mml:mi>\u03b5<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our result can be generalized to give a fully dynamic <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(f^3)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>f<\/mml:mi><mml:mn>3<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-approximate algorithm with <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(f^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>f<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most <jats:italic>f<\/jats:italic> vertices.<\/jats:p>","DOI":"10.1007\/s00453-019-00630-4","type":"journal-article","created":{"date-parts":[[2019,9,28]],"date-time":"2019-09-28T06:02:41Z","timestamp":1569650561000},"page":"1057-1080","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Deterministic Dynamic Matching in O(1) Update Time"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1612-0296","authenticated-orcid":false,"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deeparnab","family":"Chakrabarty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monika","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,28]]},"reference":[{"key":"630_CR1","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"630_CR2","unstructured":"Arar, M., Chechik, S., Cohen, S., Stein, C., Wajc, D.: Dynamic matching: reducing integral algorithms to approximately-maximal fractional algorithms. CoRR (2017). \narXiv:1711.06625"},{"key":"630_CR3","doi-asserted-by":"crossref","unstructured":"Baswana, S., Gupta, M., Sen, S.: Fully dynamic maximal matching in $$O(\\log n)$$ update time. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) (2011)","DOI":"10.1109\/FOCS.2011.89"},{"key":"630_CR4","doi-asserted-by":"crossref","unstructured":"Bernstein, A., Stein, C.: Faster fully dynamic matchings with small approximation ratios. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016)","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"630_CR5","unstructured":"Bhattacharya, S., Chakrabarty, D., Henzinger, M.: Deterministic dynamic matching in $$o(1)$$ update time. In: Proceedings of the MPS Symposium on Integer Programming and Combonatorial Optimization (IPCO) (2017)"},{"key":"630_CR6","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Design of dynamic algorithms via primal-dual method. In: Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP) (2015)","DOI":"10.1007\/978-3-662-47672-7_17"},{"key":"630_CR7","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Italiano, G.F.: Deterministic fully dynamic data structures for vertex cover and matching. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2015)","DOI":"10.1137\/1.9781611973730.54"},{"key":"630_CR8","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: New deterministic approximation algorithms for fully dynamic matching. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2016)","DOI":"10.1145\/2897518.2897568"},{"key":"630_CR9","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D.: Fully dynamic approximate maximum matching and minimum vertex cover in O(log$${}^{{3}}$$n) worst case update time. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017)","DOI":"10.1137\/1.9781611974782.30"},{"key":"630_CR10","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Kulkarni, J.: Deterministically maintaining a $$(2 +\\epsilon )$$-approximate minimum vertex cover in $$o(1\/\\epsilon ^2)$$ amortized update time. In: SODA, pp. 1872\u20131885 (2019)","DOI":"10.1137\/1.9781611975482.113"},{"key":"630_CR11","doi-asserted-by":"crossref","unstructured":"Bosek, B., Leniowski, D., Sankowski, P., Zych, A.: Online bipartite matching in offline time. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) (2014)","DOI":"10.1109\/FOCS.2014.48"},{"key":"630_CR12","unstructured":"Charikar, M., Solomon, S.: Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds. CoRR (2017). \narXiv:1711.06883"},{"key":"630_CR13","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Kumar, A., Panigrahi, D.: Online and dynamic algorithms for set cover. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2017)","DOI":"10.1145\/3055399.3055493"},{"key":"630_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, M., Peng, R.: Fully dynamic $$(1+\\epsilon )$$-approximate matchings. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) (2013)","DOI":"10.1109\/FOCS.2013.65"},{"key":"630_CR15","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D., Saranurak, T.: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2015)","DOI":"10.1145\/2746539.2746609"},{"issue":"3","key":"630_CR16","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/PL00009228","volume":"22","author":"MR Henzinger","year":"1998","unstructured":"Henzinger, M.R., Fredman, M.L.: Lower bounds for fully dynamic connectivity problems in graphs. Algorithmica 22(3), 351\u2013362 (1998)","journal-title":"Algorithmica"},{"key":"630_CR17","doi-asserted-by":"crossref","unstructured":"Neiman, O., Solomon, S.: Simple deterministic algorithms for fully dynamic maximal matching. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488703"},{"key":"630_CR18","doi-asserted-by":"crossref","unstructured":"Onak, K., Rubinfeld, R.: Maintaining a large matching and a small vertex cover. In: Proceedings of the ACM Symposium on Theory of Computing (STOC) (2010)","DOI":"10.1145\/1806689.1806753"},{"key":"630_CR19","doi-asserted-by":"crossref","unstructured":"Parter, M., Peleg, D., Solomon, S.: Local-on-average distributed tasks. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2016)","DOI":"10.1137\/1.9781611974331.ch17"},{"key":"630_CR20","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: Lower bounds for dynamic connectivity. In: Encyclopedia of Algorithms, pp. 1162\u20131167. Springer (2016)","DOI":"10.1007\/978-1-4939-2864-4_214"},{"key":"630_CR21","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"630_CR22","doi-asserted-by":"crossref","unstructured":"Solomon, S.: Fully dynamic maximal matching in constant update time. In: Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) (2016)","DOI":"10.1109\/FOCS.2016.43"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00630-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00630-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00630-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,26]],"date-time":"2020-09-26T23:33:45Z","timestamp":1601163225000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00630-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,28]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["630"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00630-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,9,28]]},"assertion":[{"value":"2 March 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}