6 citations · 12 across the 18 of their papers we have counts for
7 papers · 1 filter
Tree Containment Above Minimum Degree is FPT
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
According to the classic Chv{á}tal's Lemma from 1977, a graph of minimum degree contains every tree on vertices. Our main result is the following algorithmic "exten…
Counting Vanishing Matrix-Vector Products
Cornelius Brand, Viktoriia Korchemna, Michael Skotnica +1
Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let…
Consistency-Checking Problems: A Gateway to Parameterized Sample Complexity
Robert Ganian, Liana Khazaliya, Kirill Simonov
Recently, Brand, Ganian and Simonov introduced a parameterized refinement of the classical PAC-learning sample complexity framework. A crucial outcome of their investigation is tha…
Turán's Theorem Through Algorithmic Lens
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
The fundamental theorem of Turán from Extremal Graph Theory determines the exact bound on the number of edges in an -vertex graph that does not contain a clique of size…
Approximating Long Cycle Above Dirac's Guarantee
Fedor F. Fomin, Petr A. Golovach, Danil Sagunov +1
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit ``natural'' guarantees bringin…
A Parameterized Theory of PAC Learning
Cornelius Brand, Robert Ganian, Kirill Simonov
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the clas…
Proportionally Fair Matching with Multiple Groups
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar +1
The study of fair algorithms has become mainstream in machine learning and artificial intelligence due to its increasing demand in dealing with biases and discrimination. Along thi…