Τα περισσότερα γραφοθεωρητικά προβλήματα είναι γνωστό πως είναι NP-πλήρη στα γενικά γραφήματα. Δεν θεωρείται πίθανο να υπάρχει αλγόριθμος πολυωνυμικού χρόνου για την επίλυσή τους. Με κίνητρο το γεγονός ότι πολλά από αυτά τα προβλήματα έχουν εφαρμογές στον πραγματικό κόσμο, οι ερευνητές έχουν επικεντρωθεί στην σχεδίαση όλο και γρηγορότερων ακριβών αλγορίθμων εκθετικού χρόνου και όλο και καλύτερων προσεγγιστικών αλγορίθμων για την επίλυσής τους. Μία άλλη κατεύθυνση της έρευνας - αυτή που ακολουθούμε στην παρούσα διατριβή -, η οποία έλαβε μεγάλη ώθηση τα τελευταία χρόνια λόγω της ανακάλυψης νέων ισχυρών εργαλείων στο πλαίσιο της Παραμετροποιημένης Πολυπλοκότητας, είναι η μελέτη αυτών των προβλημάτων σε συγκεκριμένα γραφήματα που εμφανίζουν διαφόρων ειδών εσωτερική δομή. Σχεδιάζοντας αλγορίθμους που εκμεταλλεύονται αυτή την εσωτερική δομή, ενδέχεται να παράσχουμε καλύτερες εγγυήσεις σε χρόνο εκτέλεσης ή/και ποιότητα λύσης σε αυτά τα συγκεκριμένα γραφήματα. Ενδέχεται επίσης να δείξουμε ότι η δυσκολία ενός προβλήματος διατηρείται σε αυτά τα γραφήματα, παράγοντας με αυτόν τον τρόπο περαιτέρω γνώση πάνω στα είδη δομής που κάνουν το πρόβλημα δύσκολο στην επίλυση. Στην παρούσα διατριβή, μελετούμε προβλήματα συνόλου τερματικών κορυφών: δοθέντων ενός γραφήματος (με βάρη στις κορυφές) και ενός υποσυνόλου κορυφών των γραφήματος, που καλείται το σύνολο τερματικών κορυφών, αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο τέμνει (κρούει) κάθε υποσύνολο κορυφών των γραφήματος που περιέχει τερματική κορυφή και επάγει υπογράφημα που εμφανίζει συγκεκριμένη δομή που εξαρτάται από το πρόβλημα. Αυτή η κλάση προβλημάτων περιέχει εξέχοντα γραφοθεωρητικά προβλήματα τα οποία έχουν εφαρμογές τόσο εντός όσο και πέραν της Επιστήμης Υπολογιστών. Εστιάζουμε την μελέτη μας σε δύο συγκεκριμένα προβλήματα. Το ένα είναι πρόβλημα κρούσης κύκλων και είναι γνωστό στην σχετική βιβλιογραφία ως το πρόβλημα στοχευμένα άκυκλου επαγόμενου υπογραφήματος (SFVS): δοθέντων ενός γραφήματος (με βάρη στις κορυφές) και ενός συνόλου τερματικών κορυφών, αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο κρούει κάθε υποσύνολο κορυφών του γραφήματος που περιέχει τερματική κορυφή και επάγει κύκλο. Μελετούμε το SFVS σε υποκλάσεις των AT-ελεύθερων γραφημάτων και σε υποκλάσεις των χορδικών γραφημάτων, τα οποία είναι γραφήματα που είναι γνωστό ότι εμφανίζουν πλούσια εσωτερική δομή. Παρέχουμε αλγορίθμους πολυωνυμικού χρόνου για την επίλυση του έμβαρου SFVS στις ακόλουθες κλάσεις γραφημάτων: γραφήματα διαστημάτων, γραφήματα μεταθέσεων, συνδιμερή γραφήματα και γραφήματα μονοπατιών ριζωμένων δένδρων. Kαι δείχνουμε ότι το μη-έμβαρο SFVS είναι NP-πλήρες στα γραφήματα μονοπατιών μη-κατευθυντικών δένδρων. Επιπλέον, για το έμβαρο SFVS, παρέχουμε έναν αλγόριθμο για την επίλυση του στα γραφήματα με φύλλωμα το πολύ k και δείχνουμε είναι W[1]-δύσκολο παραμετροποιημένο από το k. Μελετούμε επίσης το SFVS στα H-ελεύθερα γραφήματα, τα οποία είναι γραφήματα που εμφανίζουν ένα είδος εσωτερικής δομής ως αποτέλεσμα απουσίας ενός άλλου. Για το έμβαρο SFVS, παρέχουμε έναν αλγόριθμο πολυωνυμικού χρόνου για την επίλυση του στα 4K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι NP-πλήρες στα 5K_{1}-ελεύθερα γραφήματα. Για το μη-έμβαρο SFVS, παρέχουμε έναν αλγόριθμο για την επίλυση του στα (k+1)K_{1}-ελεύθερα γραφήματα. Το SFVS αποτελεί γενίκευση του κλασικού προβλήματος άκυκλου επαγόμενου υπογραφήματος (FVS): δοθέντων ενός γραφήματος (με βάρη στις κορυφές), αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο κρούει κάθε υποσύνολο κορυφών του γραφήματος που επάγει κύκλο. Το έμβαρο FVS είναι γνωστό πως είναι επιλύσιμο σε πολυωνυμικό χρόνο στα AT-ελεύθερα γραφήματα και στα χορδικά γραφήματα. Παρέχουμε έναν αλγόριθμο για την επίλυση του στα (k+1)K_{1}-ελεύθερα γραφήματα και για το μη-έμβαρο FVS, δείχνουμε ότι είναι W[1]-δύσκολο παραμετροποιημένο από το k μέσω μίας αναγωγής η οποία είναι διαφορετική από αυτή που υπάρχει στη βιβλιογραφία. Το άλλο πρόβλημα στο οποίο εστιάζουμε είναι ένα πρόβλημα κρούσης μονοπατιών και είναι γνωστό στη σχετική βιβλιογραφία ως το πρόβλημα διαχωρισμού συνόλου κορυφών (NMC): δοθέντων ενός γραφήματος (με βάρη στις κορυφές) και ένα σύνολο τερματικών κορυφών, αναζητούμε υποσύνολο κορυφών του γραφήματος ελαχίστου μεγέθους (βάρους) το οποίο δεν περιέχει τερματικές κορυφές και κρούει κάθε υποσύνολο κορυφών του γραφήματος που επάγει μονοπάτι μεταξύ δύο τερματικών κορυφών. Για το μη-έμβαρο NMC, παρέχουμε έναν αλγόριθμο πολυωνυμικού χρόνου για την επίλυση του στα 3K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι np-πλήρες στα 4K_{1}-ελεύθερα γραφήματα μέσω μίας αναγωγής η οποία στηρίζεται στον περιορισμό ότι η λύση στο NMC δεν περιέχει τερματικές κορυφές. Με κίνητρο αυτό το γεγονός, θεωρούμε επίσης το NMC χωρίς αυτόν τον περιορισμό και το καλούμε πρόβλημα απεριόριστου διαχωρισμού συνόλου κορυφών (UNMC). Για το έμβαρο UNMC, παρέχουμε έναν αλγόριθμο πολυωνυμικού χρόνου για την επίλυση του στα 3K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι NP-πλήρες στα 4K_{1}-ελεύθερα γραφήματα. Για το μη-έμβαρο UNMC, παρέχουμε έναν αλγόριθμο για την επίλυση του στα (k+1)K_{1}-ελεύθερα γραφήματα και δείχνουμε ότι είναι W[1]-δύσκολο παραμετροποιημένο από το k. Η παρούσα διατριβή δομείται ως ακολούθως: Το Κεφάλαιο 1 αποτελεί μια εισαγωγή στο αντικείμενο μελέτης. Το Μέρος I παρέχει το απαραίτητο θεωρητικό υπόβαθρο: Στοιχεία της Θεωρίας Πολυπλοκότητας και της Θεωρίας Γραφημάτων δίνονται στα Κεφάλαια 2 και 3 αντίστοιχα και οι ορισμοί των υπό μελέτη προβλημάτων μαζί με προηγουμένως γνωστά αποτελέσματα σχετικά με την πολυπλοκότητά τους δίνονται στο Κεφάλαιο 4. Το Μέρος II παρέχει τα αποτελέσματα μας σε αλγορίθμους και πολυπλοκότητα: Μετά την παροχή των απαραίτητων προκαταρκτικών στο Κεφάλαιο 5, παρουσιάζουμε τα αποτελέσματά μας σε υποκλάσεις των AT-ελεύθερων γραφημάτων, σε υποκλάσεις των χορδικών γραφημάτων και σε Η-ελεύθερα γραφήματα στα Κεφάλαια 6, 7 και 8 αντίστοιχα. Το Κεφάλαιο 9 ολοκληρώνει την διατριβή μας με μερικά σχόλια και ανοικτά προβλήματα που παρέχουν κατευθύνσεις για μελλοντική έρευνα.