Seminar

From optimization to listing: theoretical advances in some enumeration problems

Cycle 33th Oral Defence of the Phd Thesis
30 March 2022
Start time 
11:00 am
Online
Organizer: 
Doctoral School in Mathematics
Target audience: 
University community
Attendance: 
Online
Registration email: 
Registration deadline: 
29 March 2022, 12:00
Contact person: 
Rizzi Romeo

Venue: The event will take in presence only for the Phd student and part of the commission and online through the ZOOM platform. To get the access codes please contact the secretary office (phd.maths [at] unitn.it)
Time: 11.00

Alice Raffaele - PhD in Mathematics, University of Trento

Abstract:
In this final seminar, I present the new theoretical results contained in my doctoral thesis, related to the investigation of some problems relevant in enumeration and optimization.
First, I focus on a classical enumeration problem in graph theory with several applications, such as network reliability. Given an undirected graph, the objective is to list all its bonds, i.e., its minimal cuts. I provide two new algorithms, the former having the same time complexity as the state of the art by [Tsukiyama et al., 1980], whereas the latter offers an improvement. Indeed, by refining the branching strategy of [Tsukiyama et al., 1980] and relying on some dynamic data structures by [Holm et al., 2001], it is possible to define an Õ(n)-delay algorithm to output each bond of the graph as a bipartition of the n vertices. Disregarding the polylogarithmic factors hidden in the Õ notation, this is the first algorithm to list bonds in a time linear in the number of vertices.
Then, I move to studying two well-known problems in theoretical computer science, that are checking the duality of two monotone Boolean functions, and computing the dual of a monotone Boolean function. These also are relevant in many fields, such as linear programming. [Fredman and Khachiyan, 1996] developed the first quasi-polynomial time algorithm to solve the decision problem, thus proving that it is not coNP-complete. However, no polynomial-time algorithm has been discovered yet. Here, by focusing on the symmetry of the two input objects and exploiting full covers introduced by [Boros and Makino, 2009], I define an alternative decomposition approach. This offers a strong bound which, however, in the worst case, is still the same as [Fredman and Khachiyan, 1996]. Anyway, I also show how to adapt it to obtain a polynomial-space algorithm to solve the dualization problem.

Supervisor: Romeo Rizzi (University of Verona)