2026 [ nach oben ]

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphssubmitted to STACS 2026 2026
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, i.e., graphs that deterministically change over time. In a tcc, any pair of vertices must be able to reach each other via a time-respecting path. We consider both problems of maximum open tccs (openTCC), which allow temporal paths through vertices outside the component, and closed tccs (closedTCC) which require at least one temporal path entirely within the component for every pair. We focus on the structural parameter of treewidth, tw, and the recently introduced temporal parameter of temporal path number, tpn, which is the minimum number of paths needed to fully describe a temporal graph. We prove that these parameters on their own are not sufficient for fixed parameter tractability: both openTCC and closedTCC are NP-hard even when tw=9, and closedTCC is NP-hard when tpn=6. In contrast, we prove that openTCC is in XP when parameterized by tpn. On the positive side, we show that both problem become fixed parameter tractable under various combinations of structural and temporal parameters that include, tw plus tpn, tw plus the lifetime of the graph, and tw plus the maximum temporal degree.
@preprint{deligkasTemporalComponentsPathGraphs_2025, abstract = {We study the parameterized complexity of maximum temporal connected components (tccs) in temporal graphs, i.e., graphs that deterministically change over time. In a tcc, any pair of vertices must be able to reach each other via a time-respecting path. We consider both problems of maximum open tccs (openTCC), which allow temporal paths through vertices outside the component, and closed tccs (closedTCC) which require at least one temporal path entirely within the component for every pair. We focus on the structural parameter of treewidth, tw, and the recently introduced temporal parameter of temporal path number, tpn, which is the minimum number of paths needed to fully describe a temporal graph. We prove that these parameters on their own are not sufficient for fixed parameter tractability: both openTCC and closedTCC are NP-hard even when tw=9, and closedTCC is NP-hard when tpn=6. In contrast, we prove that openTCC is in XP when parameterized by tpn. On the positive side, we show that both problem become fixed parameter tractable under various combinations of structural and temporal parameters that include, tw plus tpn, tw plus the lifetime of the graph, and tw plus the maximum temporal degree.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, booktitle = {submitted to STACS 2026}, keywords = {MSO VCdimension argyriosdeligkas connectedcomponents eduardeiben georgeskretas georgtennigkeit michelledoering parameterizedcomplexity temporalgraphs temporalpathgraph temporalpathumber temporalreachability tigerlilygoldsmith transitivity treewidth year2025}, title = {Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs}, year = 2026 }

2025 [ nach oben ]

Deligkas, Argyrios; Döring, Michelle; Eiben, Eduard; Goldsmith, Tiger-Lily; Skretas, George; Tennigkeit, Georg How Many Lines to Paint the City: Exact Edge-Cover in Temporal GraphsProceedings of the AAAI Conference on Artificial Intelligence 2025: 26498–26506
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.
@inproceedings{deligkas_HowMany_2025, abstract = {Logistics and transportation networks require a large amount of resources to realise necessary connections between locations and minimizing these resources is a vital aspect of planning research. Since such networks have dynamic connections that are only available at specific times, intricate models are needed to portray them accurately. In this paper, we study the problem of minimizing the number of resources needed to realise a dynamic network, using the temporal graphs model. In a temporal graph, edges appear at specific points in time. Given a temporal graph and a natural number k, we ask whether we can cover every temporal edge exactly once using at most k temporal journeys; in a temporal journey consecutive edges have to adhere to the order of time. We conduct a thorough investigation of the complexity of the problem with respect to four dimensions: (a) whether the type of the temporal journey is a walk, a trail, or a path; (b) whether the chronological order of edges in the journey is strict or non-strict; (c) whether the temporal graph is directed or undirected; (d) whether the start and end points of each journey are given. We almost completely resolve the complexity of these problems and provide dichotomies for each of them with respect to k.}, author = {Deligkas, Argyrios and Döring, Michelle and Eiben, Eduard and Goldsmith, Tiger-Lily and Skretas, George and Tennigkeit, Georg}, journal = {Proceedings of the AAAI Conference on Artificial Intelligence}, keywords = {aaai argyriosdeligkas eduardeiben exactedge-cover georgeskretas georgtennigkeit michelledoering parameterizedcomplexity pathcover reachability temporalgraphs temporalpathgraph temporalpathumber tigerlilygoldsmith year2025}, month = {Apr.}, number = 25, pages = {26498-26506}, title = {How Many Lines to Paint the City: Exact Edge-Cover in Temporal Graphs}, volume = 39, year = 2025 }

2023 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization 2023: 1–32
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1-bits allowed in the length-\(n\) bit string (i.e., a cardinality constraint). We investigate the natural translation of the OneMax test function to this setting, a linear function where \(B\) bits have a weight of \(1+ 1/n\) and the remaining bits have a weight of \(1\). Friedrich et al. [TCS 2020] gave a bound of \(\Theta(n^2)\) for the expected running time of the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping a \(1\) and a \(0\) simultaneously. The experimental literature proposes balanced operators, preserving the number of 1-bits, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as for classic bit mutation. Crossover together with a simple island model gives running times of \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming-distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution, we present an extensive analysis of different balanced crossover operators from the literature.
@article{friedrich2023crossover, abstract = {To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1-bits allowed in the length-\(n\) bit string (i.e., a cardinality constraint). We investigate the natural translation of the OneMax test function to this setting, a linear function where \(B\) bits have a weight of \(1+ 1/n\) and the remaining bits have a weight of \(1\). Friedrich et al. [TCS 2020] gave a bound of \(\Theta(n^2)\) for the expected running time of the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping a \(1\) and a \(0\) simultaneously. The experimental literature proposes balanced operators, preserving the number of 1-bits, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as for classic bit mutation. Crossover together with a simple island model gives running times of \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming-distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution, we present an extensive analysis of different balanced crossover operators from the literature.}, author = {Friedrich, Tobias and Kötzing, Timo and Radhakrishnan, Aishwarya and Schiller, Leon and Schirneck, Martin and Tennigkeit, Georg and Wietheger, Simon}, journal = {ACM Transactions on Evolutionary Learning and Optimization}, keywords = {aishwaryaradhakrishnan georgtennigkeit leonschiller martinschirneck simonwietheger telo timokoetzing tobiasfriedrich year2023}, pages = {1-32}, title = {Crossover for Cardinality Constrained Optimization}, volume = 3, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon Crossover for Cardinality Constrained OptimizationGenetic and Evolutionary Computation Conference (GECCO) 2022: 1399–1407
Best Paper Award (Theory Track)
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.
@inproceedings{friedrich2022crossover, abstract = {In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.}, author = {Friedrich, Tobias and Kötzing, Timo and Radhakrishnan, Aishwarya and Schiller, Leon and Schirneck, Martin and Tennigkeit, Georg and Wietheger, Simon}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {aishwaryaradhakrishnan gecco georgtennigkeit leonschiller martinschirneck simonwietheger timokoetzing tobiasfriedrich year2022}, note = {Best Paper Award (Theory Track)}, pages = {1399–1407}, title = {Crossover for Cardinality Constrained Optimization}, year = 2022 }