{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T21:04:31Z","timestamp":1776287071713,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T00:00:00Z","timestamp":1699920000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T00:00:00Z","timestamp":1699920000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["DFG Research Training Group 2434 \u201dFacets of Complexity\u201d"],"award-info":[{"award-number":["DFG Research Training Group 2434 \u201dFacets of Complexity\u201d"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006211","name":"Humboldt-Universit\u00e4t zu Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006211","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the network untangling problem introduced by Rozenshtein et al. (Data Min. Knowl. Disc. 35(1), 213\u2013247, 2021), which is a variant of\u00a0<jats:sc>Vertex Cover<\/jats:sc>on temporal graphs\u2013graphs whose edge set changes over discrete time steps. They introduce two problem variants. The goal is to select at most<jats:italic>k<\/jats:italic>time intervals for each vertex such that all time-edges are covered and (depending on the problem variant) either the maximum interval length or the total sum of interval lengths is minimized. This problem has data mining applications in finding activity timelines that explain the interactions of entities in complex networks. Both variants of the problem are NP-hard. In this paper, we initiate a multivariate complexity analysis involving the following parameters: number of vertices, lifetime of the temporal graph, number of intervals per vertex, and the interval length bound. For both problem versions, we (almost) completely settle the parameterized complexity for all combinations of those four parameters, thereby delineating the border of fixed-parameter tractability.<\/jats:p>","DOI":"10.1007\/s00224-023-10150-y","type":"journal-article","created":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T09:02:23Z","timestamp":1699952543000},"page":"103-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Disentangling the Computational Complexity of Network Untangling"],"prefix":"10.1007","volume":"68","author":[{"given":"Vincent","family":"Froese","sequence":"first","affiliation":[]},{"given":"Pascal","family":"Kunz","sequence":"additional","affiliation":[]},{"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,14]]},"reference":[{"key":"10150_CR1","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.jcss.2020.05.005","volume":"114","author":"EC Akrida","year":"2020","unstructured":"Akrida, E.C., Mertzios, G.B., Nikoletseas, S.E., et al.: How fast can we reach a target vertex in stochastic temporal graphs? J. Comput. Syst. Sci. 114, 65\u201383 (2020a)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR2","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1016\/j.jcss.2019.08.002","volume":"107","author":"EC Akrida","year":"2020","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G., et al.: Temporal vertex cover with a sliding time window. J. Comput. Syst. Sci. 107, 108\u2013123 (2020b)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR3","doi-asserted-by":"crossref","unstructured":"Boehmer, N., Froese, V., Henkel, J., et al.: Two influence maximization games on graphs made temporal. In: Proceedings of the 30th International joint conference on articial intelligence (IJCAI), pp. 45\u201351 (2021)","DOI":"10.24963\/ijcai.2021\/7"},{"issue":"3","key":"10150_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3313906","volume":"11","author":"M Bonamy","year":"2019","unstructured":"Bonamy, M., Kowalik, L., Pilipczuk, M., et al.: Tight lower bounds for the complexity of multicoloring. ACM Trans Comput Theory 11(3), 1\u201319 (2019)","journal-title":"ACM Trans Comput Theory"},{"key":"10150_CR5","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1007\/s00453-022-01018-7","volume":"85","author":"BM Bumpus","year":"2023","unstructured":"Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. Algorithmica 85, 688\u2013716 (2023)","journal-title":"Algorithmica"},{"issue":"9","key":"10150_CR6","doi-asserted-by":"publisher","first-page":"2754","DOI":"10.1007\/s00453-021-00831-w","volume":"83","author":"A Casteigts","year":"2021","unstructured":"Casteigts, A., Himmel, A., Molter, H., et al.: Finding temporal paths under waiting time constraints. Algorithmica 83(9), 2754\u20132802 (2021)","journal-title":"Algorithmica"},{"key":"10150_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., et al.: Parameterized algorithms. Springer, Cham (2015)"},{"key":"10150_CR8","doi-asserted-by":"publisher","first-page":"104,890","DOI":"10.1016\/j.ic.2022.104890","volume":"285","author":"A Deligkas","year":"2022","unstructured":"Deligkas, A., Potapov, I.: Optimizing reachability sets in temporal graphs by delaying. Inf Comput 285, 104,890 (2022)","journal-title":"Inf Comput"},{"key":"10150_CR9","volume-title":"Graph theory","author":"R Diestel","year":"2016","unstructured":"Diestel, R.: Graph theory, 5th edn. Springer, Berlin, Heidelberg (2016)","edition":"5"},{"key":"10150_CR10","unstructured":"Dondi, R.: Insights into the complexity of disentangling temporal graphs. In: Proceedings of the 23rd Italian Conference on Theoretical Computer Science (ICTCS), pp. 1\u201313 (2022)"},{"key":"10150_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Springer, London (2013)"},{"key":"10150_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2021.01.005","volume":"119","author":"T Erlebach","year":"2021","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. J. Comput. Syst. Sci. 119, 1\u201318 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR13","doi-asserted-by":"crossref","unstructured":"Fan, Y., Ju, M., Hou, S., et al.: Heterogeneous temporal graph transformer: an intelligent system for evolving android malware detection. In: Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 2831\u20132839 (2021)","DOI":"10.1145\/3447548.3467168"},{"key":"10150_CR14","doi-asserted-by":"crossref","unstructured":"Fellows, M.R., Jaffke, L., Kir\u00e1ly, A.I., et al.: What is known about vertex cover kernelization? In: Adventures Between Lower Bounds and Higher Altitudes -essays Dedicated to Juraj Hromkovi\u010d on the Occasion of his 60th Birthday, pp. 330\u2013356 (2018)","DOI":"10.1007\/978-3-319-98355-4_19"},{"key":"10150_CR15","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Springer, Berlin, Heidelberg (2006)"},{"key":"10150_CR16","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1007\/s00224-022-10069-w","volume":"66","author":"T Fluschnik","year":"2022","unstructured":"Fluschnik, T., Niedermeier, R., Rohm, V., et al.: Multistage vertex cover. Theory Comput Syst 66, 454\u2013483 (2022)","journal-title":"Theory Comput Syst"},{"issue":"16","key":"10150_CR17","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1016\/j.ipl.2010.05.029","volume":"110","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Gaspers, S., Golovach, P.A., et al.: Parameterized algorithm for eternal vertex cover. Inf. Process. Lett. 110(16), 702\u2013706 (2010)","journal-title":"Inf. Process. Lett."},{"key":"10150_CR18","doi-asserted-by":"crossref","unstructured":"Froese, V., Kunz, P., Zschoche, P.: Disentangling the computational complexity of network untangling. In: Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 2037\u20132043 (2022)","DOI":"10.24963\/ijcai.2022\/283"},{"issue":"3","key":"10150_CR19","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s00224-007-1309-3","volume":"41","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R., Wernicke, S.: Parameterized complexity of vertex cover variants. Theory Comput Syst 41(3), 501\u2013520 (2007)","journal-title":"Theory Comput Syst"},{"key":"10150_CR20","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/j.tcs.2021.04.002","volume":"868","author":"K Heeger","year":"2021","unstructured":"Heeger, K., Himmel, A., Kammer, F., et al.: Multistage graph problems on a global budget. Theoret. Comput. Sci. 868, 46\u201364 (2021)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"10150_CR21","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.physrep.2012.03.001","volume":"519","author":"P Holme","year":"2012","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal networks. Phys. Rep. 519(3), 97\u2013125 (2012)","journal-title":"Phys. Rep."},{"issue":"1","key":"10150_CR22","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1007\/s13721-022-00406-x","volume":"12","author":"MM Hosseinzadeh","year":"2023","unstructured":"Hosseinzadeh, M.M., Cannataro, M., Guzzi, P.H., et al.: Temporal networks in biology and medicine: a survey on models, algorithms, and tools. Network Modeling Analysis in Health Informatics and Bioinformatics 12(1), 10 (2023)","journal-title":"Network Modeling Analysis in Health Informatics and Bioinformatics"},{"issue":"2","key":"10150_CR23","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10150_CR24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.jcss.2012.04.004","volume":"79","author":"K Jansen","year":"2013","unstructured":"Jansen, K., Kratsch, S., Marx, D., et al.: Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci. 79(1), 39\u201349 (2013)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10458-022-09583-5","volume":"37","author":"N Klobas","year":"2023","unstructured":"Klobas, N., Mertzios, G.B., Molter, H., et al.: Interference-free walks in time: temporally disjoint paths. Auton. Agent. Multi-Agent Syst. 37, 1 (2023)","journal-title":"Auton. Agent. Multi-Agent Syst."},{"issue":"4","key":"10150_CR26","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"10150_CR27","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219\u2013230 (1980)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR28","unstructured":"Mertzios, G.B., Molter, H., Niedermeier, R., et al.: Computing maximum matchings in temporal graphs. In: Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 27:1\u201327:14 (2020)"},{"key":"10150_CR29","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.jcss.2021.03.005","volume":"120","author":"GB Mertzios","year":"2021","unstructured":"Mertzios, G.B., Molter, H., Zamaraev, V.: Sliding window temporal graph coloring. J. Comput. Syst. Sci. 120, 97\u2013115 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.04.006","volume":"634","author":"O Michail","year":"2016","unstructured":"Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theoret. Comput. Sci. 634, 1\u201323 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"10150_CR31","unstructured":"Nederlof, J.: Inclusion exclusion for hard problems. Master\u2019s thesis. Department of Information and Computer Science, Utrecht University (2008)"},{"key":"10150_CR32","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to fixed-parameter algorithms. Oxford University Press, Oxford (2006)"},{"issue":"8","key":"10150_CR33","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2009.04.002","volume":"75","author":"I Razgon","year":"2009","unstructured":"Razgon, I., O\u2019Sullivan, B.: Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci. 75(8), 435\u2013450 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"10150_CR34","doi-asserted-by":"crossref","unstructured":"Rozenshtein, P., Gionis, A.: Mining temporal networks. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 3225\u20133226 (2019)","DOI":"10.1145\/3292500.3332295"},{"key":"10150_CR35","doi-asserted-by":"crossref","unstructured":"Rozenshtein, P., Tatti, N., Gionis, A.: The network-untangling problem: from interactions to activity timelines. In: Proceedings of the joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML\/PKDD), pp. 701\u2013716 (2017)","DOI":"10.1007\/978-3-319-71249-9_42"},{"issue":"1","key":"10150_CR36","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s10618-020-00717-5","volume":"35","author":"P Rozenshtein","year":"2021","unstructured":"Rozenshtein, P., Tatti, N., Gionis, A.: The network-untangling problem: from interactions to activity timelines. Data Min. Knowl. Disc. 35(1), 213\u2013247 (2021)","journal-title":"Data Min. Knowl. Disc."},{"key":"10150_CR37","doi-asserted-by":"crossref","unstructured":"Singer, U., Guy, I., Radinsky, K.: Node embedding over temporal graphs. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 4605\u20134612 (2019)","DOI":"10.24963\/ijcai.2019\/640"},{"key":"10150_CR38","doi-asserted-by":"crossref","unstructured":"Xia, W., Li, Y., Tian, J., et al.: Forecasting interaction order on temporal graphs. In: Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pp. 1884\u20131893 (2021)","DOI":"10.1145\/3447548.3467341"},{"key":"10150_CR39","doi-asserted-by":"crossref","unstructured":"Zschoche, P., Fluschnik, T., Molter, H., et al.: The complexity of finding small separators in temporal graphs. J. Comput. Syst. Sci. 107, 72\u201392 (2020)","DOI":"10.1016\/j.jcss.2019.07.006"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10150-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10150-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10150-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T23:42:16Z","timestamp":1730504536000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10150-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,14]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["10150"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10150-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,11,14]]},"assertion":[{"value":"3 October 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}