MaxDDBS

The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory.

Definition

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

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.

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.

Computational complexity

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). The problem remains NP-hard even when restricting to only one constraint (either degree or diameter).

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 $D=1$, which was one of Karp's 21 NP-complete problems.

Bounds and relationships

The order of any graph with maximum degree $\Delta$ and diameter $D$ cannot exceed the Moore bound:

$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 $N_{\Delta ,D}$ the order of the largest graph with maximum degree $\Delta$ and diameter $D$, then for any solution $S$ of MaxDDBS with $n$ vertices:

$n\le N_{\Delta ,D}\le M_{\Delta ,D}$

Applications

MaxDDBS has diverse practical applications:

• 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.

Algorithms

A greedy heuristic algorithm has been proposed for MaxWDDBS with a worst-case approximation ratio of $\frac{\min (n,N_{\Delta ,D})}{\Delta +1}$, where $n$ is the number of vertices in the host graph. The algorithm starts with a $\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 $O(n^{1/2})$.

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).

Special cases in specific host graphs

The problem has been studied for various host graph families, with bounds established for mesh networks, hypercubes, honeycomb networks, triangular networks, butterfly networks, Beneš networks, and oxide networks.

Mesh networks

When the host graph is a $k$ -dimensional mesh, the problem relates to counting lattice points in balls under the L¹ metric.

For a mesh with $\Delta =2k$, the largest subgraph contains as many vertices as lattice points in a closed ball of radius $D/2$.

The number of lattice points $|B_k(p)|$ in a maximal ball of radius $p$ in $k$ dimensions is given by:

• For even diameter $D=2p$: These are the Delannoy numbers

• For odd diameter $D=2p+1$: These form a Riordan array of coordination sequences

Specific constructions have been developed for:

• 3D mesh with $\Delta =4$:
  • Achieves $\frac{4p^3}{3}+2p^2-\frac{4p}{3}+3$ vertices for $D=2p$
• 2D mesh with $\Delta =3$:
  • Achieves $2p^2-2p+1$ vertices for $D=2p$

These constructions are asymptotically optimal, with average degree approaching $\Delta$ as $p\to \mathrm{\infty }$.

Hypercube

For the $k$-dimensional hypercube $Q_k$, when $D\le \Delta$, there exists a subcube $Q_{\Delta }$ containing a subgraph of order:

${\Phi }_{\Delta }(D)=\sum _{i=0}^D(\genfrac{}{}{0ex}{}{\Delta }{i})$

This represents the volume of a Hamming ball of radius $D$.

External links

The MaxDDBS page in Combinatorics Wiki