Abstract
dc:descriptionIn 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.
Degree
thesis:*- Grantor dc:publisher
- University of Patras
- Year dc:date
- 2024
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Panagopoulou, Aggeliki-Panagiota
- Παναγοπούλου, Αγγελική-Παναγιώτα
Subjects
dc:subject × 12Rights
- Language dc:language
- gre
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/57218