The '''Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS)''' is a problem in graph theory.
== Definition==
Given a connected host graph <math> G </math>, an upper bound for the degree <math> \Delta </math>, and an upper bound for the diameter <math> D </math>, we look for the largest subgraph <math> S </math> of <math> G </math> with maximum degree at most <math> \Delta </math> and diameter at most <math> D </math>.<ref name="dpr12"> {{cite journal |last1=Dekker |first1=A. |last2=Pérez-Rosés |first2=H. |last3=Pineda-Villavicencio |first3=G. |last4=Watters |first4=P. |title=The Maximum Degree & Diameter-Bounded Subgraph and its Applications |journal=Journal of Mathematical Modelling and Algorithms |year=2012 |doi=10.1007/s10852-012-9182-8 |url=https://www.researchgate.net/publication/235908343_The_Maximum_Degree_Diameter-Bounded_Subgraph_and_its_Applications}} </ref>
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.<ref name="dpr12"/>
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.<ref name="dpr12"/>
== 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).<ref name="mprr12">{{cite journal |last1=Miller |first1=Mirka |last2=Pérez-Rosés |first2=Hebert |last3=Ryan |first3=Joe |title=The maximum degree and diameter-bounded subgraph in the mesh |journal=Discrete Applied Mathematics |volume=160 |issue=12 |year=2012 |pages=1782–1790 |doi=10.1016/j.dam.2012.03.035}} </ref> The problem remains NP-hard even when restricting to only one constraint (either degree or diameter).<ref name="dpr12"/>
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 <math> D = 1 </math>, which was one of Karp's 21 NP-complete problems.<ref name="dpr12"/>
== Bounds and relationships==
The order of any graph with maximum degree <math> \Delta </math> and diameter <math> D </math> cannot exceed the Moore bound:<ref name="dpr12"/>
:<math> M_{\Delta,D} = 1 + \Delta + \Delta(\Delta - 1) + \cdots + \Delta(\Delta - 1)^{D-1} </math>
This bound also serves as a theoretical upper bound for MaxDDBS. If we denote by <math> N_{\Delta,D} </math> the order of the largest graph with maximum degree <math> \Delta </math> and diameter <math> D </math>, then for any solution <math> S </math> of MaxDDBS with <math> n </math> vertices:
:<math> n \leq N_{\Delta,D} \leq M_{\Delta,D} </math>
== Applications==
MaxDDBS has diverse practical applications:<ref name="dpr12"/>
*'''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 <math> \frac{\min(n,N_{\Delta,D})}{\Delta+1} </math>, where <math> n </math> is the number of vertices in the host graph.<ref name="dpr12"/> The algorithm starts with a <math> \Delta </math>-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 <math> O(n^{1/2}) </math>.<ref name="dpr12"/>
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).<ref name="dpr12"/>
== 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.<ref name="wlp21">{{cite conference |last1=Wijerathne |first1=H.M.C. |last2=Lanel |first2=G.H.J. |last3=Perera |first3=K.K.K.R. |title=Review on Maximum Degree Diameter Bounded Subgraph Problem |conference=Proceedings of SLIIT International Conference on Advancements in Sciences and Humanities |year=2021 |pages=12–24 |url=https://www.researchgate.net/profile/Ghj-Lanel/publication/357647790_Review_on_Maximum_Degree_Diameter_Bounded_Subgraph_Problem/links/61d7d2dbb8305f7c4b285fd7/Review-on-Maximum-Degree-Diameter-Bounded-Subgraph-Problem.pdf}} </ref>
=== Mesh networks===
When the host graph is a <math> k </math> -dimensional mesh, the problem relates to counting lattice points in balls under the {{math|''L''<sup>1</sup>}} metric.<ref name="mprr12"/>
For a mesh with <math> \Delta = 2k </math>, the largest subgraph contains as many vertices as lattice points in a closed ball of radius <math> D/2 </math>.<ref name="mprr12"/>
The number of lattice points <math> |B_k(p)| </math> in a maximal ball of radius <math> p </math> in <math> k </math> dimensions is given by:<ref name="mprr12"/>
*For even diameter <math> D = 2p </math>: These are the Delannoy numbers
*For odd diameter <math> D = 2p + 1 </math>: These form a Riordan array of coordination sequences
Specific constructions have been developed for:<ref name="mprr12"/>
*3D mesh with <math> \Delta = 4 </math>: **Achieves <math> \frac{4p^3}{3} + 2p^2 - \frac{4p}{3} + 3 </math> vertices for <math> D = 2p </math> *2D mesh with <math> \Delta = 3 </math>: **Achieves <math> 2p^2 - 2p + 1 </math> vertices for <math> D = 2p </math>
These constructions are asymptotically optimal, with average degree approaching <math> \Delta </math> as <math> p \to \infty </math>.
=== Hypercube===
For the <math> k </math>-dimensional hypercube <math> Q_k </math>, when <math> D \leq \Delta </math>, there exists a subcube <math> Q_\Delta </math> containing a subgraph of order:
:<math> \Phi_\Delta(D) = \sum_{i=0}^{D} \binom{\Delta}{i} </math>
This represents the volume of a Hamming ball of radius <math> D </math>.<ref name="dpr12"/>
== External links==
[http://combinatoricswiki.org/wiki/The_Maximum_Degree-and-Diameter-Bounded_Subgraph_Problem The MaxDDBS page in Combinatorics Wiki] == References== {{reflist}}
Category:Computational problems in graph theory