Edge modification on perfect and reducible graphs with application to watermarking
Authors: Μπαντή Άννα 
Published: January 2023

Σε προβλήματα τροποποίησης γραφήματος, πρέπει να διορθώσουμε, να βελτιώσουμε ή να προσαρμόσουμε ένα γράφημα προκειμένου να πληροί συγκεκριμένες κατάλληλες ιδιότητες, ελαχιστοποιώντας ταυτόχρονα το κόστος της τροποποίησης. Η μελέτη των προβλημάτων τροποποίησης γραφημάτων είναι ύψιστης σημασίας για την επιστήμη των υπολογιστών. Τα προβλήματα τροποποίησης γραφημάτων έχουν πολλές εφαρμογές σε διαφορετικούς τομείς, όπως η βιολογία, τα μαθηματικά, η κοινωνιολογία, η μηχανική μάθηση, η εξόρυξη δεδομένων, η υπολογιστική όραση και πολλοί άλλοι τομείς. Το κύριο σημείο εστίασης αυτής της διδακτορικής διατριβής έγκειται σε δύο μέρη, το θεωρητικό και το εφαρμοσμένο μέρος των προβλημάτων τροποποίησης ακμών σε κατηγορίες τέλειων γραφημάτων και αναγώγιμων γραφημάτων. Στο θεωρητικό μέρος, μελετάμε και παρουσιάζουμε αλγόριθμους πολυωνυμικού χρόνου για το πρόβλημα ελάχιστης συμπλήρωσης (i) ενός γραφήματος και την προσθήκη μιας “ουράς” (tail) για τέσσερις υποκατηγορίες τέλειων γραφημάτων και (ii) ενός γραφήματος και την προσθήκη μιας ακμής για τη κατηγορία P4-sparse γραφημάτων. Το πρόβλημα ελάχιστης συμπλήρωσης ορίζεται ως εξής: Δεδομένης μιας οικογένειας γραφημάτων F (ή γενικότερα, μια ιδιότητα Π) και ενός γραφήματος G, το πρόβλημα συμπλήρωσης ζητά τον ελάχιστο αριθμό μη ακμών που χρειάζεται να προστεθούν στο G, ώστε το γράφημα που προκύπτει να ανήκει στην οικογένεια γραφημάτων F (ή να έχει την ιδιότητα Π). Αυτό το πρόβλημα είναι NP-complete για πολλές κλάσεις τέλειων γραφημάτων και υπάρχουν πολυωνυμικές λύσεις μόνο για ελάχιστα σύνολα συμπλήρωσης. Δεδομένου ενός γραφήματος G, ουρά uw είναι μια ακμή που συνδέει έναν κόμβο w ̸∈ V (G) με έναν κόμβο u ∈ V (G). Μελετάμε το πρόβλημα ελάχιστης συμπλήρωσης για το γράφημα G + uw σε κατηγορίες τέλειων γραφημάτων, όπως τα split, quasi- threshold, threshold και P4-sparse γραφήματα. Με βάση τις ιδιότητες της δομής των split γραφημάτων και της δεντρικής αναπαράστασης των quasi-threshold, threshold και P4-sparse γραφημάτων, παρουσιάζουμε αλγόριθμους γραμμικού χρόνου για την επίλυση αυτού του προβλήματος. Επιπρόσθετα, για την κατηγορία των P4-sparse γραφημάτων, μελετάμε το πρόβλημα ελάχιστης συμπλήρωσης ενός P4-sparse γραφήματος G με την πρόσθεση μιας μη-ακμής. Συγκεκριμένα, δοθέντος ενός P4-sparse γραφήματος G και μιας μη-ακμής xy (δηλαδή, ένα ζεύγος των μη γειτονικών κόμβων x και y) του G, υπολογίζεται ο ελάχιστος αριθμός μη ακμών του G που πρέπει να προστεθούν στο G έτσι ώστε το γράφημα που προκύπτει να είναι P4-sparse γράφημα και να περιέχει την xy ως ακμή. Για κάθε βέλτιστη λύση του προβλήματος, αποδεικνύουμε ότι υπάρχει μια βέλτιστη λύση της οποίας η μορφή είναι μία από ένα μικρό πλήθος πιθανοτήτων. Αυτό μαζί με τη λύση του προβλήματος όταν η προστιθέμενη ακμή συνδέει δύο μη γειτονικού κόμβους ενός spider γραφήματος ή συνδέει δύο κόμβους σε δυο διαφορετικές συνεκτικές συνιστώσες του γραφήματος, μας δίνει τη δυνατότητα να παρουσιάσουμε έναν αλγόριθμο γραμμικού χρόνου για το πρόβλημα. Τέλος, το εφαρμοσμένο μέρος της παρούσας διατριβής επικεντρώνεται στη μελέτη των κακόβουλων τροποποιήσεων ακμών των αναγώγιμων (reducible) γραφημάτων που χρησιμοποιούνται για την κωδικοποίηση ενός ακέραιου αριθμού ως υδατογράφημα σε ένα συγκεκριμένο σύστημα κωδικοποίησης υδατογραφήματος λογισμικού. Σε οποιαδήποτε μέθοδο υδατογράφησης λογισμικού, το πιο σημαντικό μέρος είναι η επιλογή του σωστού υδατογραφήματος, δηλαδή στην προτεινόμενη μέθοδο μας, ένα υδατογράφημα, της μορφής του αναγώγιμου γραφήματος, που είναι ανθεκτικό σε επιθέσεις τροποποίησης ακμών. Μέσω της μελέτης τέτοιων τροποποιήσεων ακμών, ταξινομούμε τα υδατογραφήματα ως ισχυρά, ενδιάμεσα ή αδύναμα και είμαστε σε θέση να δώσουμε συστάσεις για την καλύτερη επιλογή υδατογραφήματος προς χρήση.