{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,29]],"date-time":"2025-12-29T19:01:10Z","timestamp":1767034870045},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>We study the recently introduced network untangling problem, a variant of Vertex Cover on temporal graphs---graphs whose edge set changes over discrete time steps. There are two versions of this problem. The goal is to select at most k 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.\n\n\n\nBoth 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.24963\/ijcai.2022\/283","type":"proceedings-article","created":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T22:55:56Z","timestamp":1657925756000},"page":"2037-2043","source":"Crossref","is-referenced-by-count":5,"title":["Disentangling the Computational Complexity of Network Untangling"],"prefix":"10.24963","author":[{"given":"Vincent","family":"Froese","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Faculty IV, Institute of Software Engineering and Theoretical Computer Science, Algorithmics and Computational Complexity"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Kunz","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Faculty IV, Institute of Software Engineering and Theoretical Computer Science, Algorithmics and Computational Complexity"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Zschoche","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Faculty IV, Institute of Software Engineering and Theoretical Computer Science, Algorithmics and Computational Complexity"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"number":"31","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2022","name":"Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}","start":{"date-parts":[[2022,7,23]]},"theme":"Artificial Intelligence","location":"Vienna, Austria","end":{"date-parts":[[2022,7,29]]}},"container-title":["Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T07:08:48Z","timestamp":1658128128000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2022\/283"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2022\/283","relation":{},"subject":[],"published":{"date-parts":[[2022,7]]}}}