MaxDDBS

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

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 \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 \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 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 \infty . === Hypercube=== For the k -dimensional hypercube Q_k , when D \leq \Delta , there exists a subcube Q_\Delta containing a subgraph of order: \Phi_\Delta(D) = \sum_{i=0}^{D} \binom{\Delta}{i} This represents the volume of a Hamming ball of radius D . == External links== The MaxDDBS page in Combinatorics Wiki == References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353297801 under CC BY-SA 4.0; modifications have been made.