Νέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος

datacite.contributor.RelatedPersonΚοσμαδάκης, Σταύρος
datacite.contributor.RelatedPersonΚωτσιαντής, Σωτήριος
datacite.contributor.RelatedPersonΡάγγος, Όμηρος
datacite.contributor.RelatedPersonΡαπτόπουλος, Χριστόφορος
datacite.contributor.RelatedPersonΚοντογιάννης, Σπυρίδων
datacite.contributor.RelatedPersonΣταματίου, Ιωάννης
datacite.contributor.SupervisorΚαββαδίας, Δημήτριος
dc.contributor.authorΠαναγοπούλου, Αγγελική-Παναγιώτα
dc.contributor.otherPanagopoulou, Angeliki-Panagiota
dc.date.accessioned2024-02-29T11:45:44Z
dc.date.available2024-02-29T11:45:44Z
dc.date.issued2024-02-23
dc.degreedoctoralThesis
dc.description.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.
dc.description.translatedabstractIn this thesis we study an important problem in Computer Science and present new algorithms and new theoretical results for it. The problem that we study is the computation of the dual of a given hypergraph. A hypergraph is a generalization of a graph in the sense that they both consist of a set of vertices and a set of edges, but they differ in that in a graph the edges have a multiplicity of two (here we consider an edge as a set with two elements, the set of its endpoints), while in a hypergraph the edges have an arbitrary multiplicity (from 1 to n, n being the number of vertices). For this reason, in hypergraphs, the term hyperedge has been adopted instead of the term edge. Hypergraphs are used to model various entities, for example communities in a network, associations in a database, biochemical processes and many others. The dual of a hypergraph, in the sense in which the term is used in this paper, is also a hypergraph with the same set of vertices as the given one, and with set of hyperedges the set of minimal intersection sets of all hyperedges of the hypergraph. An intersection set, which we call a transversal (or hitting set), is a subset of the vertices of the hypergraph, which has a non-empty intersection with all hyperedges of the hypergraph. A minimal transversal is a transversal which is minimal in the sense that the removal of any vertex results in a set that is not a transversal, i.e. it no longer has a non-empty intersection with at least one hyperedge. Finding the dual hypergraph is an important problem with many applications, some of which are in fact a reformulation of its definition. A relatively extensive list of applications is given in this thesis, and several references are also given in the bibliography. The natural way in which the problem appears in many applications is augmented by a new application which we present, by reducing the computation of the automorphisms of a graph (or even checking the isomorphism of two graphs) to the problem of computing the dual hypergraph . Due to the fact that the algorithmic computation of the dual hypergraph implies outputting the hyperedges of the dual hypergraph, it is common to characterize this process as the generation of the dual hypergraph (DHG). The DHG problem, and its decision version, in which two hypergraphs are given and we are asked to decide whether they are dual, are studied in this thesis. There are many efficient algorithms for these problems, of which the best theoretical upper bounds have the algorithms of Fredman and Khachiyan (for the decision version of the problem), which are quasi polynomial. Part of the results of this thesis consists of studying the Fredman-Khachiyan algorithm in benchmarks which are frequently reported in the literature. We show that for these benchmarks the Fredman-Khachiyan algo- rithm is polynomial, thus justifying the observed good practical performance of the algorithm that is reported in the literature. The Fredman-Khachiyan algorithm is a “divide and conquer” algorithm, which proceeds by breaking the problem into smaller subproblems. In addition to the basic decomposition operation, a secondary reduction in the size of the subproblems is also induced by the requirement that the subproblems must be in a given form (Sperner families). We named these observed reductions em absorptions, and we studied and characterized their structure and calculated their number in the above mentioned benchmarks. The new algorithms we have presented are mainly based on modeling the decision version of the problem as a special form satisfiability problem and the DHG as a problem of generating all minimal models of a fully positive Conjunctive Normal Form. This modeling yielded two new algorithms, one which we called the Embedding Algorithm and one which we called the Subtransversal Expanding Algorithm. In both cases the main method used is the Resolution method. The Embedding algorithm proceeds by generating a new minimal model while maintai- ning a Conjunctive Normal Form, whose minimal models are the remaining ones. In terms of hypergraphs, we called the corresponding hypergraph the residual dual hypergraph. The Subtransversal Expanding algorithm uses the notion of subtrans- versal (set of vertices that can be expanded into a minimal transversal), partitioning the minimal intersections into supersets of specific subtransversals. In its current form, the Embedding algorithm is superpolynomial, while the Subtransversal Ex- pansion algorithm produces the subtransversals needed in polynomial space but it is parallelizable for the subsequent steps. Another large class of algorithms for the DHG problem are algorithms based on the multiplication method. One such algorithm is the algorithm of Kavvadias and Stavropoulos, which we improved in such a way that it now solves in polynomial time instances for which it had a superpolynomial lower bound. At the same time, another simple modification of the algorithm showed a significant improvement in its performance, as shown by several experimental results. We also dealt with the practical solution of the DHG problem based on the Resolution method, for which emphasis was placed on the rate of clauses growth, which is the main parameter in the performance of this algorithm. Finally, in the same framework, a solver of the satisfiability problem (sat-solver), the kissat program, was used and its appropriate parameterization on SAT instances derived from DHG was investigated.
dc.identifier.urihttps://hdl.handle.net/10889/26669
dc.language.isoel
dc.subjectΔυικό υπεργράφημα
dc.subjectΕλαχιστική διατέμνουσα
dc.subjectΥποδιατέμνουσα
dc.subject.alternativeDual hypergraph
dc.subject.alternativeMinimal transversal
dc.subject.alternativeSubtransversal
dc.titleΝέοι αλγόριθμοι για το πρόβλημα του δυικού υπεργραφήματος
dc.title.alternativeNew algorithms for the dual hypergraph problem

Files

Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
ΔΙΔΑΚΤΟΡΙΚΗ ΔΙΑΤΡΙΒΗ_ΠΑΝΑΓΟΠΟΥΛΟΥ.pdf
Size:
1.36 MB
Format:
Adobe Portable Document Format
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
5.02 KB
Format:
Item-specific license agreed upon to submission
Description: