IMPA Tech graduate presents seminar on algorithms

Switching roles. Accustomed to accompanying IMPA Tech’s academic seminars, graduate student Vinicius Prestes, from class 2024, took on the role of lecturer this Tuesday (2). He presented his scientific initiation work “On the Computation of a Minimal Maximal Set Cover: Exact Algorithms and Lower Bounds based on (S)ETH” to his classmates. And it was the first time that a bachelor’s student had spoken at the seminar series.

The project was carried out collectively during the directed studies of “Exact Exponential Algorithms”, supervised by Professor Uéverton. Alan Santos, Cristiane Sampaio, Felipe Ribeiro, Lucas Fraga and Marcelo Alves are also part of the research group.

Together, the undergraduates analyzed the computational limitations of solving a variant of the classic Set Cover, a fundamental problem in computing. The discussion began with a collective reading of chapters from the textbook Exact Exponential Algorithms, written by Fedor V. Fomin and Dieter Kratsch.

The group investigated a max-min version of a challenging minimization problem also known as “Set Coverage”, which consists of finding efficient combinations of data sets within a large volume of information. The aim was to create algorithms and mathematical solutions to solve the problem in the shortest possible time. While the classic problem consists of finding the smallest combination to cover all the elements provided, the research carried out analyzed the question of computing the maximum minimal combination to cover the elements, a natural variant for the subject.

“We investigated properties of Set Cover, Vertex Cover, Dominating Set and Upper Domination, which are cover problems in graphs and systems of sets. These are classic problems, which have many published studies, but we tackled a problem that didn’t have many studies, which is the Maximum Minimal Set Cover, and had an interesting opportunity to make advances. More specifically, we studied algorithms to identify this minimal maximal structure in any set system, and we came up with several results about which algorithm we can use,” explained Prestes.

In May, the article on the study was one of the three best in Brazil and was selected for oral presentation at the Scientific Initiation Work Competition (CTIC). The competition, promoted by the Brazilian Computer Society (SBC), is the most traditional in the field.

The seminar at IMPA Tech precedes the presentation in the final phase of the competition, which will take place in July, in Gramado (RS), during the SBC Congress (CSBC), the main meeting of the Computing community in Latin America.

“The presentation is of a Scientific Initiation paper that has already won an award, as it was among the three finalists out of 105 submissions. This seminar also served as training for the presentation. Colleagues were able to see what had been done and what the results were,” said Professor Uéverton.

For Ribeiro, one of the group’s members, the seminar symbolizes the completion of a months-long project. “Taking part in this research process was very important, both academically and personally. The feeling of having finished the article was already incredible, but being selected for a major event is very gratifying. Today’s presentation shows the great potential we have at IMPA Tech,” he said.