Graph sandwich problem
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ ಮತ್ತು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ, ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆಯು ಗ್ರಾಫ್ಗಳ ಒಂದು ನಿರ್ದಿಷ್ಟ ಕುಟುಂಬಕ್ಕೆ ಸೇರಿದ ಗ್ರಾಫ್ ಅನ್ನು ಕಂಡುಹಿಡಿಯುವ ಒಂದು ಸಮಸ್ಯೆಯಾಗಿದೆ ಮತ್ತು ಇತರ ಎರಡು ಗ್ರಾಫ್ಗಳ ನಡುವೆ "ಸ್ಯಾಂಡ್ವಿಚ್" ಆಗಿದೆ, ಅವುಗಳಲ್ಲಿ ಒಂದು ಸಬ್ಗ್ರಾಫ್ ಆಗಿರಬೇಕು ಮತ್ತು ಇನ್ನೊಂದು ಅಪೇಕ್ಷಿತ ಗ್ರಾಫ್ನ ಸೂಪರ್ಗ್ರಾಫ್ ಆಗಿರಬೇಕು. ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆಗಳು ನೀಡಲಾದ ಗ್ರಾಫ್ಗಳು ಗ್ರಾಫ್ಗಳ ಕುಟುಂಬಕ್ಕೆ ಸೇರಿವೆಯೇ ಎಂದು ಪರೀಕ್ಷಿಸುವ ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸುತ್ತವೆ ಮತ್ತು ಅವುಗಳ ಅನ್ವಯಗಳ ಕಾರಣದಿಂದಾಗಿ ಮತ್ತು ಗುರುತಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಗಳ ನೈಸರ್ಗಿಕ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿ ಗಮನವನ್ನು ಸೆಳೆದಿವೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆ ಹೆಚ್ಚು ನಿಖರವಾಗಿ, ಶೃಂಗದ ಸೆಟ್ V, ಕಡ್ಡಾಯ ಅಂಚಿನ ಸೆಟ್ E1, ಮತ್ತು ದೊಡ್ಡ ಅಂಚಿನ ಸೆಟ್ E2 ಅನ್ನು ನೀಡಿದರೆ, ಗ್ರಾಫ್ G = (V, E) ಅನ್ನು ಜೋಡಿ G1 = (V, E1), G2 = (V, E2) ಗೆ ಸ್ಯಾಂಡ್ವಿಚ್ ಗ್ರಾಫ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಪ್ರಾಪರ್ಟಿಗೆ ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ ಪ್ರಾಪರ್ಟಿಗೆ ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆ Π: ನಿದರ್ಶನಃ ವೆರ್ಟೆಕ್ಸ್ ಸೆಟ್ V ಮತ್ತು ಎಡ್ಜ್ ಸೆಟ್ E1-E2-V × V. ಪ್ರಶ್ನೆಃ ಗ್ರಾಫ್ G = (V, E) ಇದೆಯೇ ಎಂದರೆ E1-E2-E2 ಮತ್ತು G ಗುಣಲಕ್ಷಣವನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆಯೇ? ಗ್ರಾಫ್ಗಳ ಒಂದು ವರ್ಗದ ಗುರುತಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಯು (ಗುಣಲಕ್ಷಣ Π ಅನ್ನು ತೃಪ್ತಿಪಡಿಸುವ) ನಿರ್ದಿಷ್ಟ ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ, ಅಲ್ಲಿ E1 = E2, ಅಂದರೆ, ಐಚ್ಛಿಕ ಅಂಚಿನ ಸೆಟ್ ಖಾಲಿಯಾಗಿದೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಪೂರ್ಣವಾಗಿದ್ದು, Π ಎಂಬುದು ಸ್ವರಮೇಳದ ಗ್ರಾಫ್, ಹೋಲಿಕೆಯ ಗ್ರಾಫ್, ಕ್ರಮಪಲ್ಲಟನೆಯ ಗ್ರಾಫ್, ಸ್ವರಮೇಳದ ಉಭಯಪಕ್ಷೀಯ ಗ್ರಾಫ್ ಅಥವಾ ಸರಪಳಿಯ ಗ್ರಾಫ್ ಆಗಿರುತ್ತದೆ. ವಿಭಜಿತ ಗ್ರಾಫ್ಗಳು, ಮಿತಿ ಗ್ರಾಫ್ಗಳು ಮತ್ತು ಗ್ರಾಫ್ಗಳಿಗೆ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಇದನ್ನು ಪರಿಹರಿಸಬಹುದು, ಇದರಲ್ಲಿ ಪ್ರತಿ ಐದು ಶೃಂಗಗಳು ಗರಿಷ್ಠ ಒಂದು ನಾಲ್ಕು-ಅಕ್ಷತಂತು ಪ್ರೇರಿತ ಮಾರ್ಗವನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಪ್ರತಿಯೊಂದು ನಾಲ್ಕು-ಅಕ್ಷೀಯ ನಕ್ಷೆಗಳಿಗೆ ಎಚ್-ಫ್ರೀ ಗ್ರಾಫ್ ಸ್ಯಾಂಡ್ವಿಚ್ ಸಮಸ್ಯೆಗಳಿಗೆ ಸಂಕೀರ್ಣತೆಯ ಸ್ಥಿತಿಯನ್ನು ಸಹ ಪರಿಹರಿಸಲಾಗಿದೆ. ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು