1 citations · 2 across the 11 of their papers we have counts for
18 papers · 1 filter
Subexponential Algorithm for High Multiplicity Fair Division of Mixed Instances via Stereometry
Yuriy Dementiev, Fedor Pribytkov, Danil Sagunov
We study the problem of computing an envy-free (EF) allocation of indivisible items among agents when items come in three distinct types. Each agent holds additive valuatio…
Exploiting Spanning Trees for Directed Acyclicity
Sergei Khargeliia, Danil Sagunov
We study the weighted case of the \textsc{Maximum Acyclic Subgraph (MAS)} problem, where each edge of a given directed graph has a positive weight assigned, and the task is to find…
Learning Augmented Exact Exponential Algorithms
Tatiana Belova, Yuriy Dementiev, Danil Sagunov
The field of learning-augmented algorithms has demonstrated that machine-learned predictions can bypass worst-case lower bounds across a wide range of problems. So far, however, th…
Discounted Cuts: A Stackelberg Approach to Network Disruption
Pål Grønås Drange, Fedor V. Fomin, Petr Golovach +1
We study a Stackelberg variant of the classical Most Vital Links problem, modeled as a one-round adversarial game between an attacker and a defender. The attacker strategically rem…
Edge Clique Partition and Cover Beyond Independence
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a…
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
Fedor V. Fomin, Petr A. Golovach, Nikola Jedličková +3
The classic theorem of Gallai and Milgram (1960) generalizes several fundamental results in Graph Theory, such as Dilworth's theorem on posets and Kőnig's theorem on matchings in b…
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…
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…
Longest Cycle above Erdős-Gallai Bound
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)\geq 2 contains a cycle of length at least ad(G). We provide an algorithm that for k\geq 0 in ti…
Detours in Directed Graphs
Fedor V. Fomin, Petr A. Golovach, William Lochet +3
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Pa…
Algorithmic Extensions of Dirac's Theorem
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov +1
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every -vertex -connected graph with minimum vertex degree $δ\ge…
Diverse Pairs of Matchings
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke +2
We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph and an integer , ask whether has two (maximum/perfect) matchings w…
Maximizing Happiness in Graphs of Bounded Clique-Width
Ivan Bliznets, Danil Sagunov
Clique-width is one of the most important parameters that describes structural complexity of a graph. Probably, only treewidth is more studied graph width parameter. In this paper…
Building large k-cores from sparse graphs
Fedor V. Fomin, Danil Sagunov, Kirill Simonov
A popular model to measure network stability is the -core, that is the maximal induced subgraph in which every vertex has degree at least . For example, -cores are commonl…
On Happy Colorings, Cuts, and Structural Parameterizations
Ivan Bliznets, Danil Sagunov
We study the Maximum Happy Vertices and Maximum Happy Edges problems. The former problem is a variant of clusterization, where some vertices have already been assigned to clusters.…
Lower Bounds for the Happy Coloring Problems
Ivan Bliznets, Danil Sagunov
In this paper, we study the Maximum Happy Vertices and the Maximum Happy Edges problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were s…
Solving Target Set Selection with Bounded Thresholds Faster than
Ivan Bliznets, Danil Sagunov
In this paper we consider the Target Set Selection problem. The problem naturally arises in many fields like economy, sociology, medicine. In the Target Set Selection problem one i…