7 Search Results for "Kosinas, Evangelos"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.87
Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time

Authors: Kevin Hua, Daniel Li, Jaewoo Park, and Thatchaphol Saranurak

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

Abstract
We show the first near-linear time randomized algorithms for listing all minimum vertex cuts of polylogarithmic size that separate the graph into at least three connected components (also known as shredders) and for finding the most shattering one, i.e., the one maximizing the number of connected components. Our algorithms break the quadratic time bound by Cheriyan and Thurimella (STOC'96) for both problems that has been unimproved for more than two decades. Our work also removes an important bottleneck to near-linear time algorithms for the vertex connectivity augmentation problem (Jordan '95) and finding an even-length directed cycle in a graph, a problem shown to be equivalent to many other fundamental problems (Vazirani and Yannakakis '90, Robertson et al. '99). Note that it is necessary to list only minimum vertex cuts that separate the graph into at least three components because there can be an exponential number of minimum vertex cuts in general. To obtain a near-linear time algorithm, we have extended techniques in local flow algorithms developed by Forster et al. (SODA'20) to list shredders on a local scale. We also exploit fast queries to a pairwise vertex connectivity oracle subject to vertex failures (Long and Saranurak FOCS'22, Kosinas ESA'23). This is the first application of using connectivity oracles subject to vertex failures to speed up a static graph algorithm.
Cite as

Kevin Hua, Daniel Li, Jaewoo Park, and Thatchaphol Saranurak. Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 87:1-87:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hua_et_al:LIPIcs.ICALP.2024.87,
  author =	{Hua, Kevin and Li, Daniel and Park, Jaewoo and Saranurak, Thatchaphol},
  title =	{{Finding Most-Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{87:1--87:19},
  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.87},
  URN =		{urn:nbn:de:0030-drops-202302},
  doi =		{10.4230/LIPIcs.ICALP.2024.87},
  annote =	{Keywords: Graphs, Flows, Randomized Algorithms, Vertex Connectivity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.109
Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity

Authors: Yaowei Long and Yunfan Wang

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

Abstract
We study the sensitivity oracles problem for subgraph connectivity in the decremental and fully dynamic settings. In the fully dynamic setting, we preprocess an n-vertices m-edges undirected graph G with n_{off} deactivated vertices initially and the others are activated. Then we receive a single update D ⊆ V(G) of size |D| = d ≤ d_{⋆}, representing vertices whose states will be switched. Finally, we get a sequence of queries, each of which asks the connectivity of two given vertices u and v in the activated subgraph. The decremental setting is a special case when there is no deactivated vertex initially, and it is also known as the vertex-failure connectivity oracles problem. We present a better deterministic vertex-failure connectivity oracle with Ô(d_{⋆}m) preprocessing time, Õ(m) space, Õ(d²) update time and O(d) query time, which improves the update time of the previous almost-optimal oracle [Long and Saranurak, 2022] from Ô(d²) to Õ(d²). We also present a better deterministic fully dynamic sensitivity oracle for subgraph connectivity with Ô(min{m(n_{off} + d_{⋆}),n^{ω}}) preprocessing time, Õ(min{m(n_{off} + d_{⋆}),n²}) space, Õ(d²) update time and O(d) query time, which significantly improves the update time of the state of the art [Bingbing Hu et al., 2023] from Õ(d⁴) to Õ(d²). Furthermore, our solution is even almost-optimal assuming popular fine-grained complexity conjectures.
Cite as

Yaowei Long and Yunfan Wang. Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 109:1-109:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{long_et_al:LIPIcs.ICALP.2024.109,
  author =	{Long, Yaowei and Wang, Yunfan},
  title =	{{Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{109:1--109: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.109},
  URN =		{urn:nbn:de:0030-drops-202523},
  doi =		{10.4230/LIPIcs.ICALP.2024.109},
  annote =	{Keywords: connectivity, sensitivity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.75
Connectivity Queries Under Vertex Failures: Not Optimal, but Practical

Authors: Evangelos Kosinas

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

Abstract
We revisit once more the problem of designing an oracle for answering connectivity queries in undirected graphs in the presence of vertex failures. Specifically, given an undirected graph G with n vertices and m edges and an integer d_⋆ ≪ n, the goal is to preprocess the graph in order to construct a data structure 𝒟 such that, given a set of vertices F with |F| = d ≤ d_⋆, we can derive an oracle from 𝒟 that can efficiently answer queries of the form "is x connected with y in G⧵F?". Very recently, Long and Saranurak (FOCS 2022) provided a solution to this problem that is almost optimal with respect to the preprocessing time, the space usage, the update time, and the query time. However, their solution is highly complicated, and it seems very difficult to be implemented efficiently. Furthermore, it does not settle the complexity of the problem in the regime where d_⋆ is a constant. Here, we provide a much simpler solution to this problem, that uses only textbook data structures. Our algorithm is deterministic, it has preprocessing time and space complexity O(d_⋆ m log n), update time O(d⁴ log n), and query time O(d). These bounds compare very well with the previous best, especially considering the simplicity of our approach. In fact, if we assume that d_⋆ is a constant (d_⋆ ≥ 4), then our algorithm provides some trade-offs that improve the state of the art in some respects. Finally, the data structure that we provide is flexible with respect to d_⋆: it can be adapted to increases and decreases, in time and space that are almost proportional to the change in d_⋆ and the size of the graph.
Cite as

Evangelos Kosinas. Connectivity Queries Under Vertex Failures: Not Optimal, but Practical. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 75:1-75:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kosinas:LIPIcs.ESA.2023.75,
  author =	{Kosinas, Evangelos},
  title =	{{Connectivity Queries Under Vertex Failures: Not Optimal, but Practical}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{75:1--75:13},
  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.75},
  URN =		{urn:nbn:de:0030-drops-187289},
  doi =		{10.4230/LIPIcs.ESA.2023.75},
  annote =	{Keywords: Graphs, Connectivity, Fault-Tolerant, Oracles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.60
Computing the 4-Edge-Connected Components of a Graph: An Experimental Study

Authors: Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas

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

Abstract
The notions of edge-cuts and k-edge-connected components are fundamental in graph theory with numerous practical applications. Very recently, the first linear-time algorithms for computing all the 3-edge cuts and the 4-edge-connected components of a graph have been introduced. In this paper we present carefully engineered implementations of these algorithms and evaluate their efficiency in practice, by performing a thorough empirical study using both real-world graphs taken from a variety of application areas, as well as artificial graphs. To the best of our knowledge, this is the first experimental study for these problems, which highlights the merits and weaknesses of each technique. Furthermore, we present an improved algorithm for computing the 4-edge-connected components of an undirected graph in linear time. The new algorithm uses only elementary data structures, and is implementable in the pointer machine model of computation.
Cite as

Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph: An Experimental Study. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 60:1-60:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2022.60,
  author =	{Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos},
  title =	{{Computing the 4-Edge-Connected Components of a Graph: An Experimental Study}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{60:1--60:16},
  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.60},
  URN =		{urn:nbn:de:0030-drops-169988},
  doi =		{10.4230/LIPIcs.ESA.2022.60},
  annote =	{Keywords: Connectivity Cuts, Edge Connectivity, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.47
Computing the 4-Edge-Connected Components of a Graph in Linear Time

Authors: Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas

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

Abstract
We present the first linear-time algorithm that computes the 4-edge-connected components of an undirected graph. Hence, we also obtain the first linear-time algorithm for testing 4-edge connectivity. Our results are based on a linear-time algorithm that computes the 3-edge cuts of a 3-edge-connected graph G, and a linear-time procedure that, given the collection of all 3-edge cuts, partitions the vertices of G into the 4-edge-connected components.
Cite as

Loukas Georgiadis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing the 4-Edge-Connected Components of a Graph in Linear Time. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ESA.2021.47,
  author =	{Georgiadis, Loukas and Italiano, Giuseppe F. and Kosinas, Evangelos},
  title =	{{Computing the 4-Edge-Connected Components of a Graph in Linear Time}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{47:1--47:17},
  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.47},
  URN =		{urn:nbn:de:0030-drops-146286},
  doi =		{10.4230/LIPIcs.ESA.2021.47},
  annote =	{Keywords: Cuts, Edge Connectivity, Graph Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.20
Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice

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

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
We consider two problems regarding the computation of connectivity cuts in undirected graphs, namely identifying vertex-edge cut-pairs and identifying 2-edge cuts, and present an experimental study of efficient algorithms for their computation. In the first problem, we are given a biconnected graph G and our goal is to find all vertices v such that G⧵v is not 2-edge-connected, while in the second problem, we are given a 2-edge-connected graph G and our goal is to find all edges e such that G⧵e is not 2-edge-connected. These problems are motivated by the notion of twinless strong connectivity in directed graphs but are also of independent interest. Moreover, the computation of 2-edge cuts is a main step in algorithms that compute the 3-edge-connected components of a graph. In this paper, we present streamlined versions of two recent linear-time algorithms of Georgiadis and Kosinas that compute all vertex-edge cut-pairs and all 2-edge cuts, respectively. We compare the empirical performance of our vertex-edge cut-pairs algorithm with an alternative linear-time method that exploits the structure of the triconnected components of G. Also, we compare the empirical performance of our 2-edge cuts algorithm with the algorithm of Tsin, which was reported to be the fastest one among the previously existing for this problem. To that end, we conduct a thorough experimental study to highlight the merits and weaknesses of each technique.
Cite as

Loukas Georgiadis, Konstantinos Giannis, Giuseppe F. Italiano, and Evangelos Kosinas. Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.SEA.2021.20,
  author =	{Georgiadis, Loukas and Giannis, Konstantinos and Italiano, Giuseppe F. and Kosinas, Evangelos},
  title =	{{Computing Vertex-Edge Cut-Pairs and 2-Edge Cuts in Practice}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.20},
  URN =		{urn:nbn:de:0030-drops-137920},
  doi =		{10.4230/LIPIcs.SEA.2021.20},
  annote =	{Keywords: 2-Connectivity, Graph Algorithms, Split Components}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.38
Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems

Authors: Loukas Georgiadis and Evangelos Kosinas

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
A directed graph G = (V,E) is twinless strongly connected if it contains a strongly connected spanning subgraph without any pair of antiparallel (or twin) edges. The twinless strongly connected components (TSCCs) of a directed graph G are its maximal twinless strongly connected subgraphs. These concepts have several diverse applications, such as the design of telecommunication networks and the structural stability of buildings. A vertex v ∈ V is a twinless strong articulation point of G, if the deletion of v increases the number of TSCCs of G. Here, we present the first linear-time algorithm that finds all the twinless strong articulation points of a directed graph. We show that the computation of twinless strong articulation points reduces to the following problem in undirected graphs, which may be of independent interest: Given a 2-vertex-connected undirected graph H, find all vertices v for which there exists an edge e such that H⧵{v,e} is not connected. We develop a linear-time algorithm that not only finds all such vertices v, but also computes the number of edges e such that H⧵{v,e} is not connected. This also implies that for each twinless strong articulation point v which is not a strong articulation point in a strongly connected digraph G, we can compute the number of TSCCs in G⧵v.
Cite as

Loukas Georgiadis and Evangelos Kosinas. Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{georgiadis_et_al:LIPIcs.ISAAC.2020.38,
  author =	{Georgiadis, Loukas and Kosinas, Evangelos},
  title =	{{Linear-Time Algorithms for Computing Twinless Strong Articulation Points and Related Problems}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.38},
  URN =		{urn:nbn:de:0030-drops-133820},
  doi =		{10.4230/LIPIcs.ISAAC.2020.38},
  annote =	{Keywords: 2-connectivity, cut pairs, strongly connected components}
}
  • Refine by Author
  • 5 Kosinas, Evangelos
  • 4 Georgiadis, Loukas
  • 3 Italiano, Giuseppe F.
  • 1 Giannis, Konstantinos
  • 1 Hua, Kevin
  • Show More...

  • Refine by Classification
  • 4 Mathematics of computing → Graph algorithms
  • 4 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 3 Graph Algorithms
  • 2 Edge Connectivity
  • 2 Graphs
  • 1 2-Connectivity
  • 1 2-connectivity
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2021
  • 2 2024
  • 1 2020
  • 1 2022
  • 1 2023

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact