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, such as shortcutting and subspace enumeration, to achieve better time complexities for problems like shortest paths and maximum cut. Additionally, there is a growing interest in studying the complexity of graph problems under different parameterizations, such as treewidth and threshold rank, to identify tractable cases and develop more efficient algorithms. Noteworthy papers in this area include: A paper on the f-Critical Set problem, which proves NP-completeness for planar subcubic bipartite graphs and W[1]-hardness when parameterized by treewidth. A paper on Faster MAX-CUT on Bounded Threshold Rank Graphs, which presents a novel algorithm combining subspace enumeration and semidefinite programming to achieve a (1+O(ε))-approximation in polynomial time. A paper on Connectivity-Preserving Important Separators, which introduces a framework for handling graph separation problems with connectivity constraints and develops a new fixed-parameter-tractable algorithm for the Node Multiway Cut-Uncut problem.

Sources

Parameterized complexity of the f-Critical Set problem

Faster MAX-CUT on Bounded Threshold Rank Graphs

Shortcutting for Negative-Weight Shortest Path

A Complexity Analysis of the c-Closed Vertex Deletion Problem

How Hard is it to Explain Preferences Using Few Boolean Attributes?

A Dichotomy for 1-Planarity with Restricted Crossing Types Parameterized by Treewidth

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions

Connectivity-Preserving Important Separators: Enumeration and an Improved FPT Algorithm for Node Multiway Cut-Uncut

Built with on top of