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

Abstract

In 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 algorithm 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 secondaryreduction 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 maintaining 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 subtransversal (set of vertices that can be expanded into a minimal transversal), partitioningthe minimal intersections into supersets of specific subtransversals. In its current form, the Embedding algorithm is superpolynomial, while the Subtransversal Expansion 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.

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