Doubly Nonnegative and Semidefinite Relaxations for the Densest k-Subgraph Problem

Area of Science:

• Computer Science
• Optimization
• Graph Theory

Background:

• The densest k-subgraph (DkS) maximization problem is computationally challenging, classified as NP-hard.
• Existing methods for DkS often involve relaxation techniques to approximate solutions.

Purpose of the Study:

• To present and compare two novel relaxation methods for the DkS maximization problem.
• To analyze the approximation ratios and practical performance of these methods.

Main Methods:

• Developed a doubly nonnegative relaxation for the DkS problem.
• Introduced a tighter semidefinite relaxation compared to standard approaches.
• Established conditions for the equivalence of the two relaxation methods.

Main Results:

• Both doubly nonnegative and semidefinite relaxations provide approximation ratios for the DkS problem.
• Numerical experiments indicate that doubly nonnegative relaxation is more effective for certain DkS instances.
• The two relaxation techniques demonstrate equivalence under specific conditions.

Conclusions:

• Doubly nonnegative relaxation offers a promising alternative for solving the densest k-subgraph problem.
• The study contributes improved techniques for tackling NP-hard graph optimization problems.