Νέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος
Loading...
Date
2024-02-23
Authors
Παναγοπούλου, Αγγελική-Παναγιώτα
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Στη διατριβή αυτή μελετάται ένα σημαντικό πρόβλημα της Επιστήμης των Υπολογιστών και παρουσιάζονται νέοι αλγόριθμοι και νέα θεωρητικά αποτελέσματα για αυτό. Το πρόβλημα αυτό είναι ο υπολογισμός του δυικού ενός δοθέντος υπεργραφήματος. Ένα υπεργράφημα ομοιάζει με ένα γράφημα κατά το ότι και τα δύο αποτελούνται από ένα σύνολο κορυφών και από ένα σύνολο ακμών, διαφέρουν όμως ως προς το ότι σε ένα γράφημα οι ακμές έχουν πληθάριθμο δύο (εδώ θεωρούμε μία ακμή σαν ένα διμελές σύνολο, το σύνολο των άκρων της), ενώ σε ένα υπεργράφημα οι ακμές έχουν αυθαίρετο πληθάριθμο (από 1 έως n, n το πλήθος των κορυφών). Για τον λόγο αυτό, στα υπεργραφήματα έχει υιοθετηθεί ο όρος υπερακμή, αντί για ακμή.
Τα υπεργραφήματα χρησιμοποιούνται για τη μοντελοποίηση διαφόρων οντοτήτων, όπως για παράδειγμα κοινοτήτων σε ένα δίκτυο, συσχετίσεων σε μία βάση δεδομένων, βιοχημικών διεργασιών και πολλών άλλων.
Το δυικό ενός υπεργραφήματος, με την έννοια που χρησιμοποιείται ο όρος σε αυτήν εδώ την διατριβή, είναι και αυτό ένα υπεργράφημα με το ίδιο σύνολο κορυφών όπως το δοθέν, και με σύνολο υπερακμών το σύνολο των ελαχιστικών συνόλων τομής όλων των υπερακμών του υπεργραφήματος. Ένα σύνολο τομής, το οποίο ονομάζουμε διατέμνουσα, είναι ένα υποσύνολο των κορυφών του υπεργραφήματος, το οποίο έχει μη κενή τομή με όλες τις υπερακμές του υπεργραφήματος (hittting set ή transversal στην αγγλική βιβλιογραφία). Μία ελαχιστική διατέμνουσα (minimal transversal) είναι μία διατέμνουσα η οποία είναι ελαχιστική κατά το ότι η αφαίρεση οποιασδήποτε κορυφής συνεπάγεται ότι το σύνολο παύει να είναι διατέμνουσα, δηλαδή δεν έχει πλέον μη κενή τομή με τουλάχιστον μία υπερακμή. Η εύρεση του δυικού υπεργραφήματος είναι ένα σημαντικό πρόβλημα με πολλές εφαρμογές, κάποιες από τις οποίες είναι στην ουσία μία επαναδιατύπωση του ορισμού του. Μία σχετικά εκτενής παράθεση των εφαρμογών γίνεται σε ένα κεφάλαιο της παρούσης εργασίας, ενώ και στην βιβλιογραφία δίνονται αρκετές αναφορές. Ο φυσικός τρόπος με τον οποίο εμφανίζεται το πρόβλημα σε πολλές εφαρμογές ενισχύεται από μία νέα εφαρμογή την οποία παρουσιάζουμε, ανάγοντας τον υπολογισμό των αυτομορφισμών ενός γραφήματος (ή και τον έλεγχο του ισομορφισμού δύο γραφημάτων) στον υπολογισμό του δυικού υπεργραφήματος.
Λόγω του ότι ο αλγοριθμικός υπολογισμός του δυικού υπεργραφήματος συνεπάγεται την εμφάνιση στην έξοδο των υπερακμών του δυικού, συνηθίζεται να χαρακτηρίζεται αυτή η διαδικασία σαν γένεση του δυικού υπεργραφήματος (Dual Hypergraph Generation - DHG). To πρόβλημα DHG, καθώς και η αποφαντική του εκδοχή, κατά την οποία δίδονται δύο υπεργραφήματα και ζητείται να αποφασιστεί κατά πόσο είναι δυικά, εξετάζονται σε αυτήν τη διατριβή. Υπάρχουν πολλοί και αποτελεσματικοί αλγόριθμοι για τα προβλήματα αυτά, από τους οποίους τα καλύτερα θεωρητικά άνω φράγματα έχουν οι αλγόριθμοι των Fredman και Khachiyan (για την αποφαντική εκδοχή του προβλήματος), οι οποίοι έχουν σχεδόν πολυωνυμικό (quasi polynomial) άνω φράγμα χρόνου. Μέρος των αποτελεσμάτων της διατριβής συνίσταται στην μελέτη του αλγορίθμου Fredman-Khachiyan σε στιγμιότυπα τα οποία αναφέρονται συχνά στην βιβλιογραφία. Δείξαμε ότι για τα στιγμιότυπα αυτά ο αλγόριθμος Fredman-Khachiyan είναι πολυωνυμικός, δικαιολογώντας έτσι την παρατηρούμενη καλή πρακτική απόδοση του αλγορίθμου, όπως αναφέρεται στην βιβλιογραφία. Ο αλγόριθμος Fredman-Khachiyan είναι ένας αλγόριθμος «διαίρει και βασίλευε», ο οποίος προχωράει διασπώντας το πρόβλημα σε συνεχώς μικρότερα υποπροβλήματα. Πέρα από την βασική πράξη διάσπασης, προκαλείται επίσης και μία δευτερογενής μείωση του μεγέθους των υποπροβλημάτων από την απαίτηση τα υποπροβλήματα να βρίσκονται σε μία δεδομένη μορφή (να είναι οικογένειες Sperner). Ονομάσαμε αυτές τις μειώσεις που παρατηρούνται απορροφήσεις, μελετήσαμε και χαρακτηρίσαμε τη δομή τους και τις υπολογίσαμε επακριβώς στα προαναφερθέντα στιγμιότυπα.
Οι νέοι αλγόριθμοι που παρουσιάσαμε βασίζονται κυρίως στην μοντελοποίηση της αποφαντικής εκδοχής του προβλήματος σαν ένα πρόβλημα ικανοποιησιμότητας ειδικής μορφής και του DHG σαν πρόβλημα παραγωγής όλων των ελαχιστικών μοντέλων μίας πλήρως θετικής Συζευκτικής Κανονικής Μορφής. Η μοντελοποίηση αυτή έδωσε δύο νέους αλγορίθμους, έναν που ονομάσαμε Αλγόριθμο Ενσωμάτωσης και έναν που ονομάσαμε Αλγόριθμο Επέκτασης Υποδιατεμνουσών.
Και στις δύο περιπτώσεις η κύρια μέθοδος που χρησιμοποιείται είναι η μέθοδος της Επίλυσης (Resolution). Ο αλγόριθμος ενσωμάτωσης προχωρεί παράγοντας ένα καινούριο ελαχιστικό μοντέλο και διατηρώντας ταυτόχρονα μία Συζευκτική Κανονική Μορφή, της οποίας τα ελαχιστικά μοντέλα είναι τα υπολειπόμενα. Σε όρους υπεργραφημάτων, ονομάσαμε το αντίστοιχο υπεργράφημα υπολειπόμενο δυικό υπεργράφημα. Ο αλγόριθμος επέκτασης υποδιατεμνουσών χρησιμοποιεί την έννοια της υποδιατέμνουσας (σύνολο κορυφών που μπορεί να επεκταθεί σε ελαχιστική διατέμνουσα), διαμερίζοντας τις ελαχιστικές διατέμνουσες σε υπερσύνολα συγκεκριμένων υποδιατεμνουσών. Στην τρέχουσα μορφή του ο αλγόριθμος ενσωμάτωσης είναι υπερπολυωνυμικός, ενώ ο αλγόριθμος επέκτασης των υποδιατεμνουσών παράγει τις υποδιατέμνουσες που χρειάζεται σε πολυωνυμικό χώρο και έχει δυνατότητα παραλληλοποίησης στην συνέχεια.
Άλλη μεγάλη κατηγορία αλγορίθμων για το πρόβλημα DHG είναι οι αλγόριθμοι που βασίζονται στην πολλαπλασιαστική μέθοδο. Ένας τέτοιος αλγόριθμος είναι ο αλγόριθμος των Kavvadias και Stavropoulos, τον οποίο βελτιώσαμε με τρόπο που να επιλύει πλέον πολυωνυμικά, στιγμιότυπα για τα οποία είχε υπερπολυωνυμικό κάτω φράγμα. Παράλληλα μία άλλη απλή τροποποίηση του αλγορίθμου έδειξε μία σημαντική βελτίωση στην απόδοσή του, όπως έδειξαν πολλά πειραματικά αποτελέσματα.
Ασχοληθήκαμε επίσης με την πρακτική επίλυση του προβλήματος DHG βα-
σιζόμενοι στην μέθοδο της Επίλυσης, για την οποία δόθηκε έμφαση στον ρυθμό αύξησης των προτάσεων, που είναι και η κύρια παράμετρος στην απόδοση αυτού του αλγορίθμου. Τέλος, στα ίδια πλαίσια, χρησιμοποιήθηκε ένα πρόγραμμα επίλυσης του προβλήματος της ικανοποιησιμότητας (sat-solver), το πρόγραμμα kissat, και διερευνήθηκε η κατάλληλη παραμετροποίησή του σε στιγμιότυπα του SAT προερχόμενα από το DHG.
Description
Keywords
Δυικά υπεργραφήματα, Ελαχιστική διατέμνουσα, Υποδιατέμνουσα