Search Results

Documents authored by Hanauer, Kathrin

Document
DOI: 10.4230/LIPIcs.SAND.2025.4
On b-Matching and Fully-Dynamic Maximum k-Edge Coloring

Authors: Antoine El-Hayek, Kathrin Hanauer, and Monika Henzinger

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Given a graph G that undergoes a sequence of edge insertions and deletions, we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different colors, color as many edges of G as possible such that no two adjacent edges share the same color. While this problem is different from simply maintaining a b-matching with b = k, the two problems are related. However, maximum b-matching can be solved efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for k ≥ 2. We present new results on both problems: For b-matching, we show a new integrality gap result and we adapt Wajc’s matching sparsification scheme [David Wajc, 2020] for the case where b is a constant. Using these as basis, we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya, Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching algorithm as a black box, so any future improvement in the approximation ratio for dynamic b-matching will automatically translate into a better approximation ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update time, which guarantees a 2.16 approximation factor.
Cite as

Antoine El-Hayek, Kathrin Hanauer, and Monika Henzinger. On b-Matching and Fully-Dynamic Maximum k-Edge Coloring. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{elhayek_et_al:LIPIcs.SAND.2025.4,
  author =	{El-Hayek, Antoine and Hanauer, Kathrin and Henzinger, Monika},
  title =	{{On b-Matching and Fully-Dynamic Maximum k-Edge Coloring}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{4:1--4:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.4},
  URN =		{urn:nbn:de:0030-drops-230571},
  doi =		{10.4230/LIPIcs.SAND.2025.4},
  annote =	{Keywords: dynamic algorithm, graph algorithm, matching, b-matching, edge coloring}
}
Document
DOI: 10.4230/DagRep.14.5.12
Discrete Algorithms on Modern and Emerging Compute Infrastructure (Dagstuhl Seminar 24201)

Authors: Kathrin Hanauer, Uwe Naumann, Alex Pothen, and Robert Schreiber

Published in: Dagstuhl Reports, Volume 14, Issue 5 (2024)

Abstract
Inspired by three plenary talks by leading figures in the area of "Discrete algorithms on modern and emerging compute infrastructure" this Dagstuhl Seminar emphasized focus sessions and working groups to dive into this very versatile topic. Lively discussions between experts from academia, research laboratories, and industry yielded a number of promising prospects for follow-up activities. As always, Dagstuhl provided the perfect setting for this kind of scientific exchange.
Cite as

Kathrin Hanauer, Uwe Naumann, Alex Pothen, and Robert Schreiber. Discrete Algorithms on Modern and Emerging Compute Infrastructure (Dagstuhl Seminar 24201). In Dagstuhl Reports, Volume 14, Issue 5, pp. 12-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{hanauer_et_al:DagRep.14.5.12,
  author =	{Hanauer, Kathrin and Naumann, Uwe and Pothen, Alex and Schreiber, Robert},
  title =	{{Discrete Algorithms on Modern and Emerging Compute Infrastructure (Dagstuhl Seminar 24201)}},
  pages =	{12--24},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{5},
  editor =	{Hanauer, Kathrin and Naumann, Uwe and Pothen, Alex and Schreiber, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.5.12},
  URN =		{urn:nbn:de:0030-drops-222672},
  doi =		{10.4230/DagRep.14.5.12},
  annote =	{Keywords: Combinatorial Scientific Computing, Discrete Algorithms, Graph Algorithms, High-Performance Computing}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.18
Fully Dynamic Four-Vertex Subgraph Counting

Authors: Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized O(m^{1/2}) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m^{2/3}). Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m^{1/2-δ}). Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ}) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved by a polynomial factor.
Cite as

Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. Fully Dynamic Four-Vertex Subgraph Counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SAND.2022.18,
  author =	{Hanauer, Kathrin and Henzinger, Monika and Hua, Qi Cheng},
  title =	{{Fully Dynamic Four-Vertex Subgraph Counting}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.18},
  URN =		{urn:nbn:de:0030-drops-159608},
  doi =		{10.4230/LIPIcs.SAND.2022.18},
  annote =	{Keywords: Dynamic Graph Algorithms, Subgraph Counting, Motif Search}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.SAND.2022.1
Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk)

Authors: Kathrin Hanauer, Monika Henzinger, and Christian Schulz

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.
Cite as

Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Recent Advances in Fully Dynamic Graph Algorithms (Invited Talk). In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 1:1-1:47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SAND.2022.1,
  author =	{Hanauer, Kathrin and Henzinger, Monika and Schulz, Christian},
  title =	{{Recent Advances in Fully Dynamic Graph Algorithms}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{1:1--1:47},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.1},
  URN =		{urn:nbn:de:0030-drops-159434},
  doi =		{10.4230/LIPIcs.SAND.2022.1},
  annote =	{Keywords: fully dynamic graph algorithms, survey}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.13
O'Reach: Even Faster Reachability in Large Graphs

Authors: Kathrin Hanauer, Christian Schulz, and Jonathan Trummer

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

Abstract
One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can s reach t via a path? We revisit existing techniques and combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O'Reach can be easily combined with previously developed solutions for the problem or run standalone. In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph, but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn't necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.
Cite as

Kathrin Hanauer, Christian Schulz, and Jonathan Trummer. O'Reach: Even Faster Reachability in Large Graphs. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 13:1-13:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SEA.2021.13,
  author =	{Hanauer, Kathrin and Schulz, Christian and Trummer, Jonathan},
  title =	{{O'Reach: Even Faster Reachability in Large Graphs}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{13:1--13:24},
  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.13},
  URN =		{urn:nbn:de:0030-drops-137856},
  doi =		{10.4230/LIPIcs.SEA.2021.13},
  annote =	{Keywords: Reachability, Static Graphs, Graph Algorithms, Reachability Index, Algorithm Engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2020.14
Faster Fully Dynamic Transitive Closure in Practice

Authors: Kathrin Hanauer, Monika Henzinger, and Christian Schulz

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract
The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered. In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.
Cite as

Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Faster Fully Dynamic Transitive Closure in Practice. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SEA.2020.14,
  author =	{Hanauer, Kathrin and Henzinger, Monika and Schulz, Christian},
  title =	{{Faster Fully Dynamic Transitive Closure in Practice}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.14},
  URN =		{urn:nbn:de:0030-drops-120887},
  doi =		{10.4230/LIPIcs.SEA.2020.14},
  annote =	{Keywords: Dynamic Graph Algorithms, Reachability, Transitive Closure}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact