Στην παρούσα εργασία μελετώνται πυρήνες και παραμετρικοί αλγόριθμοι για το πρόβλημα ΣΥΝΟΛΟ ΑΝΑΔΡΑΣΗΣ ΚΟΡΥΦΩΝ τόσο για κατευθυνόμενα όσο και για μη κατευθυνόμενα γραφήματα. Στο πρόβλημα αυτό σκοπός μας είναι η διαγραφή το πολύ k κορυφών ενός γραφήματος G ώστε το γράφημα που θα προκύψει να είναι άκυκλο. Το πρόβλημα αυτό είναι NP-Hard, οπότε η έρευνα έχει στραφεί σε εναλλακτικούς τρόπους για την επίλυσή του (προσεγγιστικοί αλγόριθμοι, ευριστικές μέθοδοι, κ.ά.). Ένας από τους τρόπους αυτούς είναι με παραμετρικούς αλγόριθμους, στους οποίους επικεντρώνεται η παρούσα εργασία.
Στα μη κατευθυνόμενα γραφήματα υπάρχει πυρήνας μεγέθους O(k^2) για την γενική περίπτωση. Στα κατευθυνόμενα γραφήματα είναι ανοιχτό πρόβλημα η ύπαρξη πυρήνα πολυωνυμικού μεγέθους για την γενική περίπτωση, ωστόσο στην παρούσα εργασία μελετάται η περίπτωση που η παράμετρος στο πρόβλημά μας είναι το Σύνολο Ανάδρασης Κορυφών για το αντίστοιχο μη κατευθυνόμενο γραφήμα, που έχει πυρήνα μεγέθους O(k^4).
Όσον αφορά τους αλγόριθμους για τα μη κατευθυνόμενα γραφήματα, κυρίως χρησιμοποιούνται συνδυαστικά επιχειρήματα για την εύρεση της πολυπλοκότητάς τους, ενώ σε μια περίπτωση χρησιμοποιήκε πρόγραμμα σε Python για κάποιους υπολογισμούς. Για τα κατευθυνόμενα γραφήματα, χρησιμοποιούνται εργαλεία της θεωρίας γραφημάτων όπως οι τομές και οι διαχωριστές ενώ χρησιμοποιούνται και κάποιες πιο αφηρημένες δομές που ονομάζονται ε-δομές για την εύρεση συνόλου ανάδρασης. Η πολυπλοκότητα των αλγορίθμων αυτών προκύπτει πάλι με συνδυαστικά επιχειρήματα.
Το ΣΥΝΟΛΟ ΑΝΑΔΡΑΣΗΣ ΚΟΡΥΦΩΝ είναι ένα εκτενώς μελετημένο πρόβλημα στην Παραμετρική Πολυπλοκότητα με πληθώρα εφαρμογών στα Λειτουργικά Συστήματα, στην κατασκευή κυκλωμάτων VLSI αλλά και στην εύρεση γονιδίων που ευθύνονται για τον καρκίνο και ανήκει σε μια μεγαλύτερη κατηγορία προβλημάτων που αφορούν Σύνολα Ανάδρασης. Παρόμοιο πρόβλημα είναι το ΣΥΝΟΛΟ ΑΝΑΔΡΑΣΗΣ ΤΟΞΩΝ το οποίο επίσης λύνεται με τους αλγόριθμους για το ΣΥΝΟΛΟ ΑΝΑΔΡΑΣΗΣ ΚΟΡΥΦΩΝ.