Densest Subgraph

Reference:

1. A Convex-Programming Approach for Efficient Directed Densest Subgraph Discovery

2. Efficient and Scalable Directed Densest Subgraph Discovery

UDS problem

Definition

The Undirected Densest Subgraph (DS) problem is defined as follows:

where is the number of edges in the subgraph induced by . ### Linear Program

TBD.

DDS problem

Definition

The Directed Densest Subgraph (DDS) problem is defined as follows: where is the number of edges from to .

Linear Program

The DDS problem can be formulated as the following linear program:

And we have two theorems:

Theorem 1

For a fixed , consider two arbitrary sets ,, and let . Then .

Theorem 2

Given a feasible solution to , we can construct an -induced subgraph such that .

By setting in theorem 1, we have:

From theorem 2, we have .

So

Dual Program

The dual program of the DDS problem can be formulated as follows:

Quadratic Program

The dual program can be transformed into a quadratic program (QP) as follows: