Καλησπέρα,
Στην 4η σειρά προτεινόμενων ασκήσεων, στην άσκηση 5, ζητείται να αποδειχθεί ότι το Min Leaf Spanning Tree (1) και το Steiner Tree (2) είναι NP complete προβλήματα.
Θα ήθελα να ρωτήσω ποια είναι η "διαίσθηση" για να επιλέξουμε για το (1) αναγωγή από το Hamilton Path ενώ για το (2) από το Vertex Cover, δεδομένου ότι τα 2 προβλήματα μοιάζουν αρκετά;
(Όσες αποδείξεις βρήκα online ακολουθούν τις ίδιες αναγωγές με τις λύσεις που δίνονται χωρίς να εξηγούν κάπως πώς κατέληξαν σε αυτές τις επιλογές).
Ευχαριστώ εκ των προτέρων!