Edge modification on perfect and reducible graphs with application to watermarking

Abstract

In graph modification problems, we have to repair, improve, or adjust a graph to satisfy appropriate properties while minimizing the cost of the modification. The study of graph modification problems is crucial to computer science as they find applications in different areas, such as biology, mathematics, sociology, machine learning, data mining, and computer vision. This PhD thesis has a theoretical and a more applied part, both related to edge modification problems on classes of graphs. For the theoretical part, we study and present polynomial algorithms for the minimum completion problem (i) of a graph with a “tail” for four subclasses of perfect graphs and (ii) of a graph and an added edge for the class of P4-sparse graphs. The minimum completion (fill-in) problem is defined as follows: Given a graph family F (more generally, a property Π) and a graph G, the completion problem asks for the minimum number of non-edges needed to be added to G so that the resulting graph belongs to the graph family F (or has property Π). This problem is NP-complete for many subclasses of perfect graphs and polynomial solutions are available only for minimal completion sets. Given a graph G, a tail uw is an edge connecting a vertex w ̸∈ V (G) to a vertex u ∈ V (G). We study the minimum completion problem for the graph G+uw for the classes of split, quasi-threshold, threshold, and P4-sparse graphs. Based on properties of the structure of split graphs and of the tree representation of quasi-threshold, threshold, and P4-sparse graphs, we present linear-time algorithms to solve this problem. Additionally, for the class of P4-sparse graphs, we study the minimum completion problem of a P4-sparse graph G with an added edge. For any optimal solution of the problem, we prove that there is an optimal solution whose form is of one of a small number of possibilities. This along with the solution of the problem when the added edge connects two non-adjacent vertices of a spider or connects two vertices in different connected components of the graph enables us to present a linear-time algorithm for the problem. The applied part of this thesis focuses on the study of malicious edge modifications of reducible graphs used to encode an integer number as a watermark in a specific software watermarking codec system. The most important step in any software watermarking method is the choice of the right watermark, which, in the watermarking system we study, is a watermark producing a reducible graph in which edge modifications can be detected. Through the study of such edge modifications, we classify watermarks as strong, intermediate, or weak and we are able to give recommendations for the best choice of watermarks to use.

Σε προβλήματα τροποποίησης γραφήματος, πρέπει να διορθώσουμε, να βελτιώσουμε ή να προσαρμόσουμε ένα γράφημα προκειμένου να πληροί συγκεκριμένες κατάλληλες ιδιότητες, ελαχιστοποιώντας ταυτόχρονα το κόστος της τροποποίησης. Η μελέτη των προβλημάτων τροποποίησης γραφημάτων είναι ύψιστης σημασίας για την επιστήμη των υπολογιστών. Τα προβλήματα τροποποίησης γραφημάτων έχουν πολλές εφαρμογές σε διαφορετικούς τομείς, όπως η βιολογία, τα μαθηματικά, η κοινωνιολογία, η μηχανική μάθηση, η εξόρυξη δεδομένων, η υπολογιστική όραση και πολλοί άλλοι τομείς. Το κύριο σημείο εστίασης αυτής της διδακτορικής διατριβής έγκειται σε δύο μέρη, το θεωρητικό και το εφαρμοσμένο μέρος των προβλημάτων τροποποίησης ακμών σε κατηγορίες τέλειων γραφημάτων και αναγώγιμων γραφημάτων. Στο θεωρητικό μέρος, μελετάμε και παρουσιάζουμε αλγόριθμους πολυωνυμικού χρόνου για το πρόβλημα ελάχιστης συμπλήρωσης (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) γραφημάτων που χρησιμοποιούνται για την κωδικοποίηση ενός ακέραιου αριθμού ως υδατογράφημα σε ένα συγκεκριμένο σύστημα κωδικοποίησης υδατογραφήματος λογισμικού. Σε οποιαδήποτε μέθοδο υδατογράφησης λογισμικού, το πιο σημαντικό μέρος είναι η επιλογή του σωστού υδατογραφήματος, δηλαδή στην προτεινόμενη μέθοδο μας, ένα υδατογράφημα, της μορφής του αναγώγιμου γραφήματος, που είναι ανθεκτικό σε επιθέσεις τροποποίησης ακμών. Μέσω της μελέτης τέτοιων τροποποιήσεων ακμών, ταξινομούμε τα υδατογραφήματα ως ισχυρά, ενδιάμεσα ή αδύναμα και είμαστε σε θέση να δώσουμε συστάσεις για την καλύτερη επιλογή υδατογραφήματος προς χρήση.