Advances in Graph and Hypergraph Algorithms

The field of graph and hypergraph algorithms is rapidly advancing, with a focus on developing efficient and scalable solutions for complex problems. Recent research has explored new approaches to disentangling hyperedges, subhypergraph counting, and hyperedge prediction, leading to improved performance and accuracy in various applications. Notably, innovative uses of category theory and parameterized complexity have enabled the development of more effective algorithms for tasks such as diameter computation and VC-dimension calculation. Furthermore, advancements in logic-based algorithmic meta-theorems have led to single exponential FPT time and polynomial space solutions for problems like treedepth. Some noteworthy papers in this area include: Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension, which presents a new framework for computing diameter in graphs with bounded VC-dimension. HyperSearch: Prediction of New Hyperedges through Unconstrained yet Efficient Search, which proposes a novel search-based algorithm for hyperedge prediction that efficiently evaluates unconstrained candidate sets.

Sources

Disentangling Hyperedges through the Lens of Category Theory

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension

HyperSearch: Prediction of New Hyperedges through Unconstrained yet Efficient Search

The Parameterized Complexity of Computing the VC-Dimension

On Algorithmic Meta-Theorems for Solution Discovery: Tractability and Barriers

Finding 4-Additive Spanners: Faster, Stronger, and Simpler

Efficient recognition algorithms for $(1,2)$-, $(2,1)$- and $(2,2)$-graphs

The vertex visibility number of graphs

A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays

Built with on top of