Advances in Graph Algorithms and Complexity

The field of graph algorithms and complexity is witnessing significant developments, with a focus on improving the efficiency and scalability of algorithms for various graph problems. Researchers are exploring new techniques and approaches to tackle long-standing challenges, such as the development of faster algorithms for graph optimization problems and the improvement of approximation ratios for NP-hard problems. Notably, there have been breakthroughs in the design of deterministic algorithms for graph problems, including the construction of Gomory-Hu trees and the approximation of longest common subsequences. Additionally, researchers are investigating the complexity of graph problems under various parameterizations, such as treewidth and vertex cover number, to better understand the inherent difficulty of these problems. Some noteworthy papers in this area include: The paper on Deterministic Almost-Linear-Time Gomory-Hu Trees, which presents a breakthrough algorithm for constructing Gomory-Hu trees in almost-linear time. The paper on Deterministic Longest Common Subsequence Approximation in Near-Linear Time, which provides a deterministic algorithm for approximating the longest common subsequence of two sequences in near-linear time.

Sources

String Consensus Problems with Swaps and Substitutions

Budget and Profit Approximations for Spanning Tree Interdiction

Improved 2-Approximate Shortest Paths for close vertex pairs

Deterministic Almost-Linear-Time Gomory-Hu Trees

Structural Parameters for Steiner Orientation

Pathwidth of 2-Layer $k$-Planar Graphs

Perfect Graph Modification Problems: An Integer Programming Approach

Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane

Settling Weighted Token Swapping up to Algorithmic Barriers

Deterministic Longest Common Subsequence Approximation in Near-Linear Time

Built with on top of