Νέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος
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
Δυικό υπεργράφημα, Ελαχιστική διατέμνουσα, Υποδιατέμνουσα