MaxDDBS

The maximum degree-and-diameter-bounded subgraph problem (MaxDDBS) is a problem in graph theory.

Given a connected host graph G, an upper bound for the degree d, and an upper bound for the diameter k, we look for the largest subgraph S of G with maximum degree at most d and diameter at most k. This problem contains the degree diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). 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).

References

1. The MaxDDBS page in Combinatorics Wiki