Computing Densest k-Subgraph with Structural Parameters

2022/07/20 by Hanaka, Tesshu
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2207.09803

Abstract

Densest k-Subgraph is the problem to find a vertex subset S of size k such that the number of edges in the subgraph induced by S is maximized. In this paper, we show that Densest k-Subgraph is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distance-hereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a 2-approximation 2^\tc(G)/2n^O(1)-time algorithm where \tc(G) is the twin cover number of an input graph G.

Related

• Planted Models for the Densest k-Subgraph Problem
• The Dense k Subgraph problem
• Finding large and small dense subgraphs
• Detecting High Log-Densities -- an O(n¹/4) Approximation for Densest k-Subgraph
• Near-Optimal Fully Dynamic Densest Subgraph