Degree-constrained spanning tree
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಡಿಗ್ರಿ-ನಿರ್ಬಂಧಿತ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಎಂದರೆ ಗರಿಷ್ಠ ಶೃಂಗದ ಡಿಗ್ರಿ ಒಂದು ನಿರ್ದಿಷ್ಟ ಸ್ಥಿರಾಂಕ k ಗೆ ಸೀಮಿತವಾಗಿರುವ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ. ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ ನಿರ್ದಿಷ್ಟ k ಗೆ ಅಂತಹ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಹೊಂದಿದೆಯೇ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುವುದು ಡಿಗ್ರಿ-ನಿರ್ಬಂಧಿತ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯಾನ ಇನ್ಪುಟ್ಃ n-ನೋಡ್ ನಿರ್ದೇಶಿಸದ ಗ್ರಾಫ್ G (V, E); ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ k <n. ಪ್ರಶ್ನೆಃ G ಯಾವುದೇ ನೋಡ್ k ಗಿಂತ ಹೆಚ್ಚಿನ ಡಿಗ್ರಿ ಹೊಂದಿರದ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಹೊಂದಿದೆಯೇ? ಎನ್ಪಿ-ಸಂಪೂರ್ಣತೆ ಈ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದೆ. ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಮಾರ್ಗ ಸಮಸ್ಯೆಯಿಂದ ಕಡಿಮೆಯಾಗುವುದರಿಂದ ಇದನ್ನು ತೋರಿಸಬಹುದು. kಯನ್ನು 2 ಮೌಲ್ಯಕ್ಕೆ ನಿಗದಿಪಡಿಸಲಾಗಿದ್ದರೂ ಅದು NP-ಪೂರ್ಣವಾಗಿ ಉಳಿಯುತ್ತದೆ. ಸಮಸ್ಯೆಯನ್ನು ಡಿಗ್ರಿ ≤ k ಆಗಿರಬೇಕು ಎಂದು ವ್ಯಾಖ್ಯಾನಿಸಿದರೆ, ಡಿಗ್ರಿ-ಸೀಮಿತ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀನ k = 2 ಪ್ರಕರಣವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಪಥದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಡಿಗ್ರಿ-ನಿರ್ಬಂಧಿತ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರವು ತೂಕದ ರೇಖಾಚಿತ್ರದಲ್ಲಿ, ಡಿಗ್ರಿ-ನಿರ್ಬಂಧಿತ ಕನಿಷ್ಠ ವಿಸ್ತಾರವಾದ ಮರವು (ಡಿಸಿಎಂಎಸ್ಟಿ) ಡಿಗ್ರಿ-ನಿರ್ಬಂಧಿತ ವಿಸ್ತಾರವಾದ ಮರವಾಗಿದ್ದು, ಅದರ ಅಂಚುಗಳ ಮೊತ್ತವು ಕನಿಷ್ಠ ಸಂಭವನೀಯ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಡಿಸಿಎಂಎಸ್ಟಿಯನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಜೆನೆಟಿಕ್ ಮತ್ತು ಆಂಟ್-ಬೇಸ್ಡ್ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಬಲ್ಲ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಪ್ರಸ್ತಾಪಿಸಲಾಗಿದೆ. ಅಪ್ರಾಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಒಂದು ಪುನರಾವರ್ತಿತ ಬಹುಪದ ಸಮಯದ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನೀಡುತ್ತದೆ, ಇದು ಗ್ರಾಫ್ ಅನ್ನು ನೀಡಿದರೆ, ಗರಿಷ್ಠ ಡಿಗ್ರಿಗಿಂತ ದೊಡ್ಡದಾಗಿರದ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಎಲ್ಲಾ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀಗಳ ಮೇಲೆ ಕನಿಷ್ಠ ಸಾಧ್ಯವಾದ ಗರಿಷ್ಠ ಡಿಗ್ರಿ ಇರುತ್ತದೆ. ಹೀಗಾಗಿ, ಅಂತಹ ಅಲ್ಗಾರಿದಮ್ ಗರಿಷ್ಠ ಡಿಗ್ರಿ ಅಥವಾ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ. ಉಲ್ಲೇಖಗಳು ಮರವನ್ನು ವ್ಯಾಪಿಸಿರುವ ಎನ್. ಪಿ.-ಸಂಪೂರ್ಣ ಸಮಸ್ಯೆಗಳು