Advances in Graph Algorithms and Network Design

The field of graph algorithms and network design is witnessing significant developments, with a focus on designing efficient algorithms for complex network problems. Researchers are exploring new techniques, such as random spanning trees and sum-of-squares hierarchies, to tackle challenges in network design and analysis. Notably, innovative algorithms for finding cliques in random intersection graphs and computing maximum-weight sparse subgraphs have been proposed, demonstrating the potential for improved solutions to long-standing problems. Furthermore, advancements in identifying codes and perfect matching problems have shed light on the limitations and possibilities of kernelization and logspace constructions. Overall, the field is moving towards more efficient and robust algorithms for network design and analysis. Noteworthy papers include: The paper on using random spanning trees in survivable networks design, which presents an algorithm for generating k-edge connected graphs with a near-optimal number of edges. The paper on robust algorithms for finding cliques in random intersection graphs via sum-of-squares, which obtains the first efficient algorithms for recovering the community structure of random intersection graphs. The paper on quadratic-time algorithm for the maximum-weight (k, ℓ)-sparse subgraph problem, which provides the first O(n^2 + m)-time algorithm for computing a maximum-weight (k, ℓ)-sparse subgraph.

Sources

Using random spanning trees in survivable networks design

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem

Identifying Codes Kernelization Limitations

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs

Built with on top of