13 Search Results for "Smulewicz, Marcin"

Document
DOI: 10.4230/LIPIcs.STACS.2026.42
Computing Twin-Width via Treedepth and Vertex Integrity

Authors: Robert Ganian and Mathis Rocton

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Twin-width is a graph parameter that has become central to explaining the fixed-parameter tractability of first-order model checking across many graph classes. Despite its algorithmic importance, computing twin-width remains poorly understood: even recognizing graphs of twin-width at most four is NP-hard, and no fixed-parameter approximations parameterized by twin-width itself are known. A recent approach towards breaking this barrier focuses on first developing fixed-parameter algorithms for computing or approximating twin-width under parameterizations distinct from twin-width. Our first result establishes that approximating twin-width is fixed-parameter tractable when parameterized by treedepth, thereby breaking the long-standing barrier that all previous tractable parameterizations were based on deletion distance. The proof proceeds via oriented twin-width, yielding the first constructive evidence that this variant may be easier to handle algorithmically. As our second main result, we show that computing twin-width exactly is fixed-parameter tractable with respect to vertex integrity. This constitutes the first non-trivial parameterized algorithm for computing optimal contraction sequences.
Cite as

Robert Ganian and Mathis Rocton. Computing Twin-Width via Treedepth and Vertex Integrity. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 42:1-42:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2026.42,
  author =	{Ganian, Robert and Rocton, Mathis},
  title =	{{Computing Twin-Width via Treedepth and Vertex Integrity}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{42:1--42:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.42},
  URN =		{urn:nbn:de:0030-drops-255318},
  doi =		{10.4230/LIPIcs.STACS.2026.42},
  annote =	{Keywords: twin-width, fixed-parameter algorithms, treedepth, vertex integrity}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.3
Parameterized Maximum Node-Disjoint Paths

Authors: Michael Lampis and Manolis Vasilakis

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of the famous Node-Disjoint Paths problem, where we are given an undirected graph G, k (demand) pairs of vertices (s_i, t_i), and an integer 𝓁, and are asked whether there exist at least 𝓁 vertex-disjoint paths in G whose endpoints are given pairs. This problem has been intensely studied from both the approximation and parameterized complexity point of view and is notably known to be intractable by standard structural parameters, such as tree-depth, as well as the combined parameter 𝓁 plus pathwidth. We present several results improving and clarifying this state of the art, with an emphasis towards FPT approximation. Our main positive contribution is to show that the problem’s intractability can be overcome using approximation: We show that for several of the structural parameters for which the problem is hard, most notably tree-depth, the problem admits an efficient FPT approximation scheme, returning a (1-ε)-approximate solution in time f(td,ε)n^𝒪(1). We manage to obtain these results by comprehensively mapping out the structural parameters for which the problem is FPT if 𝓁 is also a parameter, hence showing that understanding 𝓁 as a parameter is key to the problem’s approximability. This, in turn, is a problem we are able to solve via a surprisingly simple color-coding algorithm, which relies on identifying an insightful problem-specific variant of the natural parameter, namely the number of vertices used in the solution. The results above are quite encouraging, as they indicate that in some situations where the problem does not admit an FPT algorithm, it is still solvable almost to optimality in FPT time. A natural question is whether the FPT approximation algorithm we devised for tree-depth can be extended to pathwidth. We resolve this negatively, showing that under the Parameterized Inapproximability Hypothesis no FPT approximation scheme for this parameter is possible, even in time f(pw,ε)n^g(ε). We thus precisely determine the parameter border where the problem transitions from "hard but approximable" to "inapproximable". Lastly, we strengthen existing lower bounds by replacing W[1]-hardness by XNLP-completeness for parameter pathwidth, and improving the n^o(√{td}) ETH-based lower bound for tree-depth to (the optimal) n^o(td).
Cite as

Michael Lampis and Manolis Vasilakis. Parameterized Maximum Node-Disjoint Paths. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lampis_et_al:LIPIcs.IPEC.2025.3,
  author =	{Lampis, Michael and Vasilakis, Manolis},
  title =	{{Parameterized Maximum Node-Disjoint Paths}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.3},
  URN =		{urn:nbn:de:0030-drops-251357},
  doi =		{10.4230/LIPIcs.IPEC.2025.3},
  annote =	{Keywords: ETH, Maximum Node-Disjoint Paths, Parameterized Complexity, PIH}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.17
Treedepth Inapproximability and Exponential ETH Lower Bound

Authors: Édouard Bonnet, Daniel Neuen, and Marek Sokołowski

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a 2^{O(k²)} n-time exact algorithm and a polynomial-time O(OPT log^{3/2} OPT)-approximation algorithm, where the former algorithm returns an elimination forest of height k (witnessing that treedepth is at most k) for the n-vertex input graph G, or correctly reports that G has treedepth larger than k, and OPT is the actual value of the treedepth. On the complexity side, exactly computing treedepth is NP-complete, but the known reductions do not rule out a polynomial-time approximation scheme (PTAS), and under the Exponential Time Hypothesis (ETH) only exclude a running time of 2^o(√n) for exact algorithms. We show that 1.0003-approximating Treedepth is NP-hard, and that exactly computing the treedepth of an n-vertex graph requires time 2^Ω(n), unless the ETH fails. We further derive that there exist absolute constants δ, c > 0 such that any (1+δ)-approximation algorithm requires time 2^Ω(n/log^c n). We do so via a simple direct reduction from Satisfiability to Treedepth, inspired by a reduction recently designed for Treewidth [STOC '25].
Cite as

Édouard Bonnet, Daniel Neuen, and Marek Sokołowski. Treedepth Inapproximability and Exponential ETH Lower Bound. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2025.17,
  author =	{Bonnet, \'{E}douard and Neuen, Daniel and Soko{\l}owski, Marek},
  title =	{{Treedepth Inapproximability and Exponential ETH Lower Bound}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.17},
  URN =		{urn:nbn:de:0030-drops-251494},
  doi =		{10.4230/LIPIcs.IPEC.2025.17},
  annote =	{Keywords: treedepth, lower bounds, approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.26
Faster Dynamic 2-Edge Connectivity in Directed Graphs

Authors: Loukas Georgiadis, Konstantinos Giannis, and Giuseppe F. Italiano

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Let G be a directed graph with n vertices and m edges. We present a deterministic algorithm that maintains the 2-edge-connected components of G under a sequence of m edge insertions, with a total running time of O(n² log n). This significantly improves upon the previous best bound of O(mn) for graphs that are not very sparse. After each insertion, our algorithm supports the following queries with asymptotically optimal efficiency: - Test in constant time whether two query vertices v and w are 2-edge-connected in G. - Report in O(n) time all the 2-edge-connected components of G. Our approach builds on the recent framework of Georgiadis, Italiano, and Kosinas [FOCS 2024] for computing the 3-edge-connected components of a directed graph in linear time, which leverages the minset-poset technique of Gabow [TALG 2016]. Additionally, we provide a deterministic decremental algorithm for maintaining 2-edge-connectivity in strongly connected directed graphs. Given a sequence of m edge deletions, our algorithm maintains the 2-edge-connected components in total time n^(2+o(1)), while supporting the same queries as the incremental algorithm. This result assumes that the edges of a fixed spanning tree of G and of its reverse graph G^R are not deleted. Previously, the best known bound for the decremental problem was O(mn log n), obtained by a randomized algorithm without restrictions on the deletions. In contrast to prior dynamic algorithms for 2-edge-connectivity in directed graphs, our method avoids the incremental computation of dominator trees, thereby circumventing the known conditional lower bound of Ω(mn).
Cite as

Loukas Georgiadis, Konstantinos Giannis, and Giuseppe F. Italiano. Faster Dynamic 2-Edge Connectivity in Directed Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 26:1-26:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2025.26,
  author =	{Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F.},
  title =	{{Faster Dynamic 2-Edge Connectivity in Directed Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{26:1--26:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.26},
  URN =		{urn:nbn:de:0030-drops-244945},
  doi =		{10.4230/LIPIcs.ESA.2025.26},
  annote =	{Keywords: Connectivity, dynamic algorithms, directed graphs}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.20
Routing Few Robots in a Crowded Network

Authors: Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko, and M. S. Ramanujan

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
In Graph Coordinated Motion Planning, we are given a graph G some of whose vertices are occupied by robots, and we are asked to route k marked robots to their destinations while avoiding collisions and without exceeding a given budget 𝓁 on the number of robot moves. We continue the recent investigation of the problem [ICALP 2024], focusing on the parameter k that captures the task of routing a small number of robots in a possibly crowded graph. We prove that the problem is W[1]-hard parameterized by 𝓁 even for k = 1, but fixed-parameter tractable parameterized by k plus the treedepth of G. We complement the latter algorithm with an NP-hardness reduction which shows that both parameters are necessary to achieve tractability.
Cite as

Argyrios Deligkas, Eduard Eiben, Robert Ganian, Iyad Kanj, Dominik Leko, and M. S. Ramanujan. Routing Few Robots in a Crowded Network. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deligkas_et_al:LIPIcs.WADS.2025.20,
  author =	{Deligkas, Argyrios and Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Leko, Dominik and Ramanujan, M. S.},
  title =	{{Routing Few Robots in a Crowded Network}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{20:1--20:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.20},
  URN =		{urn:nbn:de:0030-drops-242516},
  doi =		{10.4230/LIPIcs.WADS.2025.20},
  annote =	{Keywords: graph coordinated motion planning, parameterized complexity, treedepth}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2025.2
Higher Connectivity in Directed Graphs (Invited Talk)

Authors: Giuseppe F. Italiano

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The computation of edge-connected components in directed and undirected graphs is a well studied problem that is motivated by several applications (see, e.g., [Hiroshi Nagamochi and Toshihide Ibaraki, 2008]). Let G = (V,E) be a strongly connected directed graph with m edges and n vertices. An edge e ∈ E is a strong bridge if G ⧵ e is not strongly connected. More generally, a set of edges C ⊆ E is a cut if G ⧵ C is not strongly connected. If |C| = k then we refer to C as a k-sized cut of G. Hence, a strong bridge is a 1-sized cut of G. A digraph G is k-edge-connected if it has no (k-1)-cuts. We say that two vertices v and w are k-edge-connected, and we denote this relation by v ↔_{k} w, if there are k edge-disjoint directed paths from v to w and k edge-disjoint directed paths from w to v. (Note that a path from v to w and a path from w to v need not be edge-disjoint). By Menger’s theorem [Karl Menger, 1927], v ↔_{k} w if and only if the removal of any set of at most k-1 edges leaves v and w in the same strongly connected component. We define a k-edge-connected component of a digraph G = (V,E) as a maximal subset U ⊆ V such that u ↔_{k} v for all u, v ∈ U. The k-edge-connected components of G form a partition of V, since v ↔_{k} w is an equivalence relation [Loukas Georgiadis et al., 2016]. Connectivity-related problems are known to be much more difficult in directed graphs than in undirected graphs (see, e.g., [Harold N. Gabow, 2016; Monika Henzinger et al., 2020; Ken-Ichi Kawarabayashi and Mikkel Thorup, 2018]). Indeed, there is a fundamental difference in the structure of the cuts in the two scenarios. Specifically, it has been established more than 60 years ago [Gomory and Hu, 1961] that edge cuts in undirected graphs have a nice structure, as defined by the Gomory-Hu tree (or cut tree), which plays a special role in identifying, for any k, the k-edge-connected components of undirected graphs. Furthermore, many efficient algorithms for computing Gomory-Hu trees are available (see e.g., [Amir Abboud et al., 2021; Amir Abboud et al., 2022; Amir Abboud et al., 2023; Chen et al., 2022; Hariharan et al., 2007; Li et al., 2022]). On the contrary, in directed graphs edge cuts have a more complicated structure, and it was proved by Benczúr [Benczúr, 1995] that in this case cut trees do not even exist. It is thus not surprising that, while it is known how to compute the k-edge-connected components of undirected graphs in linear time for k ≤ 5 [Harold N. Gabow, 2000; Zvi Galil and Giuseppe F. Italiano, 1991; Loukas Georgiadis et al., 2021; John E. Hopcroft and Robert E. Tarjan, 1973; Kosinas, 2024; Wojciech Nadara et al., 2021; Hiroshi Nagamochi and Toshihide Ibaraki, 1992; Robert E. Tarjan, 1972; Yung H. Tsin, 2009], the situation is more challenging for directed graphs, where linear-time algorithms are only known for k ≤ 2 [Robert E. Tarjan, 1972; Loukas Georgiadis et al., 2020]. Also, as argued in [Loukas Georgiadis et al., 2023], there is a substantial increase in the inherent difficulty of the problem of computing k-edge-connected components in digraphs for k = 3 compared to k = 2. Indeed, for k = 2 any pair of vertices s,t that are not 2-edge-connected can be separated by only O(n) s-t min-cuts of size 1, for which we can define a total order [Giuseppe F. Italiano et al., 2012]. For k = 3, any pair of vertices s,t that are 2-edge-connected but not 3-edge-connected, can be separated by as many as O(n²) s-t min-cuts of size 2, which are also not totally ordered. This makes it difficult to explore the effect of removing each such cut of size 2 on the strong connectivity of the graph, similar to what was done for the case of k = 2 [Loukas Georgiadis et al., 2020]. Until recently, the best-known bound for computing the k-edge-connected components of a digraph, for constant k ≥ 3, was O(mn) by Nagamochi and Watanabe [Hiroshi Nagamochi and Toshimasa Watanabe, 1993]. Georgiadis et al. [Loukas Georgiadis et al., 2023] presented a randomized (Monte-Carlo) algorithm that computes the 3-edge-connected components of a digraph with m edges in Õ(m^{3/2}) time. Their algorithm involves a nontrivial extension of the framework of [Forster et al., 2020; Nanongkai et al., 2019] for deciding whether a digraph is (k+1)-edge-connected. It applies a local search procedure [Shiri Chechik et al., 2017; Forster et al., 2020] for identifying 2-in or 2-out sets, i.e., vertex sets S ⊆ V such that there are at most 2 edges from V ⧵ S to S or from S to V⧵ S. After finding such a set S, [Loukas Georgiadis et al., 2023] applies an efficient graph operation for replacing S with a gadget of small size that preserves the pairwise connectivity among the vertices of V ⧵ S. As in [Forster et al., 2020; Nanongkai et al., 2019], local search is initiated from sampled edges, but the overall scheme is more complicated to guarantee that enough 2-in sets or 2-out sets are identified that separate vertices that are not 3-edge-connected. Recently, Georgiadis, Italiano and Kosinas [Georgiadis et al., 2024] improved significantly the bound of [Loukas Georgiadis et al., 2023] by showing how to compute the 3-edge-connected components of a digraph in linear time with a deterministic algorithm. Their algorithm differs substantially from [Loukas Georgiadis et al., 2023], as it is based on a new characterization of 2-sized cuts in digraphs, which requires new techniques and a suitable combination of the notions of 2-connectivity-light graphs [Loukas Georgiadis et al., 2023] and of maximally edge-disjoint strongly divergent spanning trees [Loukas Georgiadis and Robert E. Tarjan, 2015; Robert E. Tarjan, 1976]. In particular, Georgiadis, Italiano and Kosinas [Georgiadis et al., 2024] showed how to modify the minset-poset technique of Gabow [Harold N. Gabow, 2016], in order to find the 3-edge-connected components of a digraph with m edges in O(m) time. In the invited talk, I will survey some of this recent work on higher connectivity on directed graphs.
Cite as

Giuseppe F. Italiano. Higher Connectivity in Directed Graphs (Invited Talk). In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 2:1-2:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{italiano:LIPIcs.MFCS.2025.2,
  author =	{Italiano, Giuseppe F.},
  title =	{{Higher Connectivity in Directed Graphs}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{2:1--2:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.2},
  URN =		{urn:nbn:de:0030-drops-241096},
  doi =		{10.4230/LIPIcs.MFCS.2025.2},
  annote =	{Keywords: Connectivity, Directed graphs, Graph algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.95
Fully Dynamic Strongly Connected Components in Planar Digraphs

Authors: Adam Karczmarz and Marcin Smulewicz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintaining an implicit representation of the SCCs within Õ(n^{6/7}) worst-case time per update. The data structure supports, in O(log²{n}) time, reporting vertices of any specified SCC (with constant overhead per reported vertex) and aggregating vertex information (e.g., computing the maximum label) over all the vertices of that SCC. Furthermore, it can maintain global information about the structure of SCCs, such as the number of SCCs, or the size of the largest SCC. To the best of our knowledge, no fully dynamic SCCs data structures with sublinear update time have been previously known for any major subclass of digraphs. Our result should be contrasted with the n^{1-o(1)} amortized update time lower bound conditional on SETH, which holds even for dynamically maintaining whether a general digraph has more than two SCCs.
Cite as

Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95,
  author =	{Karczmarz, Adam and Smulewicz, Marcin},
  title =	{{Fully Dynamic Strongly Connected Components in Planar Digraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.95},
  URN =		{urn:nbn:de:0030-drops-202388},
  doi =		{10.4230/LIPIcs.ICALP.2024.95},
  annote =	{Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.68
On Fully Dynamic Strongly Connected Components

Authors: Adam Karczmarz and Marcin Smulewicz

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We consider maintaining strongly connected components (SCCs) of a directed graph subject to edge insertions and deletions. For this problem, we show a randomized algebraic data structure with conditionally tight O(n^1.529) worst-case update time. The only previously described subquadratic update bound for this problem [Karczmarz, Mukherjee, and Sankowski, STOC'22] holds exclusively in the amortized sense. For the less general dynamic strong connectivity problem, where one is only interested in maintaining whether the graph is strongly connected, we give an efficient deterministic black-box reduction to (arbitrary-pair) dynamic reachability. Consequently, for dynamic strong connectivity we match the best-known O(n^1.407) worst-case upper bound for dynamic reachability [van den Brand, Nanongkai, and Saranurak FOCS'19]. This is also conditionally optimal and improves upon the previous O(n^1.529) bound. Our reduction also yields the first fully dynamic algorithms for maintaining the minimum strong connectivity augmentation of a digraph.
Cite as

Adam Karczmarz and Marcin Smulewicz. On Fully Dynamic Strongly Connected Components. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ESA.2023.68,
  author =	{Karczmarz, Adam and Smulewicz, Marcin},
  title =	{{On Fully Dynamic Strongly Connected Components}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.68},
  URN =		{urn:nbn:de:0030-drops-187211},
  doi =		{10.4230/LIPIcs.ESA.2023.68},
  annote =	{Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.79
Computing Treedepth in Polynomial Space and Linear FPT Time

Authors: Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
The treedepth of a graph G is the least possible depth of an elimination forest of G: a rooted forest on the same vertex set where every pair of vertices adjacent in G is bound by the ancestor/descendant relation. We propose an algorithm that given a graph G and an integer d, either finds an elimination forest of G of depth at most d or concludes that no such forest exists; thus the algorithm decides whether the treedepth of G is at most d. The running time is 2^𝒪(d²)⋅n^𝒪(1) and the space usage is polynomial in n. Further, by allowing randomization, the time and space complexities can be improved to 2^𝒪(d²)⋅n and d^𝒪(1)⋅n, respectively. This improves upon the algorithm of Reidl et al. [ICALP 2014], which also has time complexity 2^𝒪(d²)⋅n, but uses exponential space.
Cite as

Wojciech Nadara, Michał Pilipczuk, and Marcin Smulewicz. Computing Treedepth in Polynomial Space and Linear FPT Time. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 79:1-79:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nadara_et_al:LIPIcs.ESA.2022.79,
  author =	{Nadara, Wojciech and Pilipczuk, Micha{\l} and Smulewicz, Marcin},
  title =	{{Computing Treedepth in Polynomial Space and Linear FPT Time}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{79:1--79:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.79},
  URN =		{urn:nbn:de:0030-drops-170175},
  doi =		{10.4230/LIPIcs.ESA.2022.79},
  annote =	{Keywords: treedepth, FPT, polynomial space}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.71
Determining 4-Edge-Connected Components in Linear Time

Authors: Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, and Marek Sokołowski

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In this work, we present the first linear time deterministic algorithm computing the 4-edge-connected components of an undirected graph. First, we show an algorithm listing all 3-edge-cuts in a given 3-edge-connected graph, and then we use the output of this algorithm in order to determine the 4-edge-connected components of the graph.
Cite as

Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz, and Marek Sokołowski. Determining 4-Edge-Connected Components in Linear Time. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nadara_et_al:LIPIcs.ESA.2021.71,
  author =	{Nadara, Wojciech and Radecki, Mateusz and Smulewicz, Marcin and Soko{\l}owski, Marek},
  title =	{{Determining 4-Edge-Connected Components in Linear Time}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{71:1--71:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.71},
  URN =		{urn:nbn:de:0030-drops-146523},
  doi =		{10.4230/LIPIcs.ESA.2021.71},
  annote =	{Keywords: graphs, connectivity, cuts}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.66
Many Visits TSP Revisited

Authors: Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study the Many Visits TSP problem, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space O*(5ⁿ). They also show a polynomial space algorithm running in time O(16^{n+o(n)}). In this work, we show three main results: - A randomized polynomial space algorithm in time O*(2^n D), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ε)-approximation in time O*(2ⁿε^{-1}). Improving the constant 2 in these results would be a major breakthrough, as it would result in improving the O*(2ⁿ)-time algorithm for Directed Hamiltonian Cycle, which is a 50 years old open problem. - A tight analysis of Berger et al.’s exponential space algorithm, resulting in an O*(4ⁿ) running time bound. - A new polynomial space algorithm, running in time O(7.88ⁿ).
Cite as

Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström. Many Visits TSP Revisited. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kowalik_et_al:LIPIcs.ESA.2020.66,
  author =	{Kowalik, {\L}ukasz and Li, Shaohua and Nadara, Wojciech and Smulewicz, Marcin and Wahlstr\"{o}m, Magnus},
  title =	{{Many Visits TSP Revisited}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{66:1--66:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.66},
  URN =		{urn:nbn:de:0030-drops-129329},
  doi =		{10.4230/LIPIcs.ESA.2020.66},
  annote =	{Keywords: many visits traveling salesman problem, exponential algorithm}
}
  • Refine by Type
  • 13 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 7 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 5 Smulewicz, Marcin
  • 3 Nadara, Wojciech
  • 2 Ganian, Robert
  • 2 Italiano, Giuseppe F.
  • 2 Karczmarz, Adam
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Parameterized complexity and exact algorithms
  • 5 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Dynamic graph algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 5 treedepth
  • 2 Connectivity
  • 2 dynamic reachability
  • 2 dynamic strong connectivity
  • 2 dynamic strongly connected components
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact