Advances in Graph Algorithms and Distributed Computing

The field of graph algorithms and distributed computing is witnessing significant developments, with a focus on improving the efficiency and scalability of algorithms for various graph problems. Research is moving towards designing faster and more efficient algorithms for problems such as searching in trees, finding cycles, and solving multicut problems. Notably, there is a growing interest in developing algorithms for planar graphs and almost-planar graphs, which are common in real-world applications. Additionally, distributed computing is becoming increasingly important, with researchers exploring new techniques for solving graph problems in a distributed setting. Some noteworthy papers in this area include:

  • A study that presents an O(log log n)-approximation algorithm for searching in trees with heavy group sets of fixed size, which can be computed in 2^O(log^2k) * poly(n) time.
  • A paper that provides an almost-optimal FPT algorithm and kernel for the T-Cycle problem on planar graphs, with a time complexity of 2^O(sqrt(k) log k) * n.
  • A work that introduces a new distributed interactive proof for planarity, which uses exponentially shorter proofs compared to the state-of-the-art bounds.

Sources

Searching in trees with heavy group sets of fixed size

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings

Deterministic Distributed DFS via Cycle Separators in Planar Graphs

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right

Built with on top of