MaxDDBS

Given a connected host graph ${\displaystyle G}$, an upper bound for the degree ${\displaystyle \Delta }$, and an upper bound for the diameter ${\displaystyle D}$, we look for the largest subgraph ${\displaystyle S}$ of ${\displaystyle G}$ with maximum degree at most ${\displaystyle \Delta }$ and diameter at most ${\displaystyle D}$.^[1]

This problem is also referred to as the Degree-Diameter Subgraph Problem, as it contains the degree diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). Despite being a natural generalization of the Degree-Diameter Problem, MaxDDBS only began to be investigated in 2011, while research in the Degree-Diameter Problem has been active since the 1960s.^[1]

There is also a weighted version of the problem (MaxWDDBS) where edges have positive integral weights, and the diameter is measured as the sum of weights along the shortest path.^[1]

Regarding its computational complexity, the problem is NP-hard, and not in APX (i.e. it cannot be approximated to within a constant factor in polynomial time).^[2] The problem remains NP-hard even when restricting to only one constraint (either degree or diameter).^[1]

The Largest Degree-Bounded Subgraph Problem is NP-hard when the subgraph must be connected, while the Maximum Diameter-Bounded Subgraph becomes the maximum clique problem for ${\displaystyle D=1}$, which was one of Karp's 21 NP-complete problems.^[1]

The order of any graph with maximum degree ${\displaystyle \Delta }$ and diameter ${\displaystyle D}$ cannot exceed the Moore bound:^[1]

${\displaystyle M_{\Delta ,D}=1+\Delta +\Delta (\Delta -1)+\cdots +\Delta (\Delta -1)^{D-1}}$

This bound also serves as a theoretical upper bound for MaxDDBS. If we denote by ${\displaystyle N_{\Delta ,D}}$ the order of the largest graph with maximum degree ${\displaystyle \Delta }$ and diameter ${\displaystyle D}$, then for any solution ${\displaystyle S}$ of MaxDDBS with ${\displaystyle n}$ vertices:

${\displaystyle n\leq N_{\Delta ,D}\leq M_{\Delta ,D}}$

MaxDDBS has diverse practical applications:^[1]

• Parallel and distributed computing: Communication time is crucial in parallel processing. Identifying a subnetwork of bounded degree and diameter within a parallel architecture enables efficient computation.
• Network security and botnets: In botnet analysis, attackers may select subnetworks with specific degree and diameter constraints to maximize damage while avoiding detection. Understanding MaxDDBS helps predict attacking network parameters and develop defensive measures.
• Biological networks: The problem has been applied to protein interaction networks to identify network cores. Bounding both degree and diameter (rather than diameter alone) can reveal richer interaction patterns.

A greedy heuristic algorithm has been proposed for MaxWDDBS with a worst-case approximation ratio of ${\displaystyle {\frac {\min(n,N_{\Delta ,D})}{\Delta +1}}}$, where ${\displaystyle n}$ is the number of vertices in the host graph.^[1] The algorithm starts with a ${\displaystyle \Delta }$-star and grows the subgraph by adding edges incident to live vertices until no more edges can be added while maintaining the degree constraint.

For the diameter-bounded variant alone, an algorithm exists with approximation ratio ${\displaystyle O(n^{1/2})}$.^[1]

Experimental studies on various host graphs show that the greedy algorithm often performs significantly better than its theoretical worst-case bound suggests, such as on antiprism graphs or random graphs (Watts-Strogatz and Barabási-Albert models).^[1]