Επιλογή NP complete προβλήματος για τις αναγωγές των Min Leaf Spanning Tree και Steiner Tree σε NP complete

Question

Καλησπέρα,

Στην 4η σειρά προτεινόμενων ασκήσεων, στην άσκηση 5, ζητείται να αποδειχθεί ότι το Min Leaf Spanning Tree (1) και το Steiner Tree (2) είναι NP complete προβλήματα.

Θα ήθελα να ρωτήσω ποια είναι η "διαίσθηση" για να επιλέξουμε για το (1) αναγωγή από το Hamilton Path ενώ για το (2) από το Vertex Cover, δεδομένου ότι τα 2 προβλήματα μοιάζουν αρκετά;

(Όσες αποδείξεις βρήκα online ακολουθούν τις ίδιες αναγωγές με τις λύσεις που δίνονται χωρίς να εξηγούν κάπως πώς κατέληξαν σε αυτές τις επιλογές).

Ευχαριστώ εκ των προτέρων!

Answer 1

Τα δύο πρόβλήματα (Min Leaf Spanning Tree και Steiner tree) είναι εντελώς διαφορετικά ως προς το φύση τους. Για το Min Leaf Spanning Tree, η επιλογή του Hamilton Path είναι προφανής, πιστεύω. Το Min Leaf Spanning Tree είναι γενίκευση του Hamilton Path (το Hamilton Path είναι ένα spanning tree με 2 μόλις φύλλα). Για το Steiner tree, η επιλογή του Vertex Cover δεν είναι προφανής και δεν υπάρχει άλλος ιδιαίτερος λόγος επιλογής από το γεγονός ότι απλά το reduction γίνεται σχετικά εύκολα.