The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory.
Definition Given a connected host graph G {\displaystyle G} , an upper bound for the degree Δ {\displaystyle \Delta } , and an upper bound for the diameter D {\displaystyle D} , we look for the largest subgraph S {\displaystyle S} of G {\displaystyle G} with maximum degree at most Δ {\displaystyle \Delta } and diameter at most D {\displaystyle 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 {\displaystyle D=1} , which was one of Karp's 21 NP-complete problems.
Bounds and relationships The order of any graph with maximum degree Δ {\displaystyle \Delta } and diameter D {\displaystyle D} cannot exceed the Moore bound:
M Δ , D = 1 + Δ + Δ ( Δ − 1 ) + ⋯ + Δ ( Δ − 1 ) D − 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 N Δ , D {\displaystyle N_{\Delta ,D}} the order of the largest graph with maximum degree Δ {\displaystyle \Delta } and diameter D {\displaystyle D} , then for any solution S {\displaystyle S} of MaxDDBS with n {\displaystyle n} vertices:
n ≤ N Δ , D ≤ M Δ , D {\displaystyle n\leq N_{\Delta ,D}\leq 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 min ( n , N Δ , D ) Δ + 1 {\displaystyle {\frac {\min(n,N_{\Delta ,D})}{\Delta +1}}} , where n {\displaystyle n} is the number of vertices in the host graph. 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 O ( n 1 / 2 ) {\displaystyle 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.
… excerpt ends here. Continue reading the full article.
