Danil Sagunov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Danil Sagunov has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Fedor V. Fomin
Department of Informatics, University of Bergen
11 shared publications - Petr A. Golovach
Department of Informatics, University of Bergen
11 shared publications - Ivan Bliznets
University of Groningen
10 shared publications - Kirill Simonov
University of Bergen, Bergen, Norway
10 shared publications - Artur Riazanov
Saint Petersburg Department of Steklov Institute of Mathematics of Russian Academy of Sciences, Saint Petersburg, Russia
2 shared publications - Dmitry Itsykson
Ben-Gurion University of the Negev, Beer Sheva, Israel
2 shared publications
Latest Publications
- 11 November 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 87
Efficient Constructions of EFX Allocations for Two Types of Indivisible Goods
We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX)—an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While prior work has established EFX existence for settings with at most three distinct valuations (HV, Ghosal, et al. 2025) and for two types of goods (Gorantla et al. 2023), the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasilinear time when there are two types of goods, given that the valuations are positive. This result strengthens the existing work of (Gorantla et al. 2023), which only guarantees the existence of EFX allocations without ensuring Pareto optimality. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation.
- 11 November 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 87
Efficient Constructions of EFX Allocations for Two Types of Indivisible Goods
We study the problem of fairly and efficiently allocating indivisible goods among agents with additive valuations. We focus on envy-freeness up to any good (EFX)—an important fairness notion in fair division of indivisible goods. A central open question in this field is whether EFX allocations always exist for any number of agents. While prior work has established EFX existence for settings with at most three distinct valuations (HV, Ghosal, et al. 2025) and for two types of goods (Gorantla et al. 2023), the general case remains unresolved. In this paper, we extend the existent knowledge by proving that EFX allocations satisfying Pareto optimality (PO) always exist and can be computed in quasilinear time when there are two types of goods, given that the valuations are positive. This result strengthens the existing work of (Gorantla et al. 2023), which only guarantees the existence of EFX allocations without ensuring Pareto optimality. Our findings demonstrate a fairly simple and efficient algorithm constructing an EFX+PO allocation.
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 276-285
Path Cover, Hamiltonicity, and Independence Number: An FPT Perspective
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 276-285
Open AccessPath Cover, Hamiltonicity, and Independence Number: An FPT Perspective
- Open Access
- 19 April 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Partial Minimum Satisfiability: Fine-Grained Analysis
There is a well-known approach to cope with NP-hard problems in practice: reduce the given problem to SAT or Max-SAT and run a SAT or a Max-SAT solver. This method is very efficient since SAT/Max-SAT solvers are extremely well-studied, as well as the complexity of these problems. At IJCAI-2011, Li et al. proposed an alternative to this approach and suggested the Partial Minimum Satisfiability problem as a reduction target for NP-hard problems. They developed the MinSatz solver and showed that reducing to Partial Min-SAT and using MinSatz is in some cases more efficient than reductions to SAT or Max-SAT. Since then many results connected to the Partial Min-SAT problem were published. However, to the best of our knowledge, the worst-case complexity of Partial Min-SAT has not been studied up until now. Our goal is to fix the issue and show a O*((2 - ε)m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time.
- 19 April 2026
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 85
Open AccessPartial Minimum Satisfiability: Fine-Grained Analysis
There is a well-known approach to cope with NP-hard problems in practice: reduce the given problem to SAT or Max-SAT and run a SAT or a Max-SAT solver. This method is very efficient since SAT/Max-SAT solvers are extremely well-studied, as well as the complexity of these problems. At IJCAI-2011, Li et al. proposed an alternative to this approach and suggested the Partial Minimum Satisfiability problem as a reduction target for NP-hard problems. They developed the MinSatz solver and showed that reducing to Partial Min-SAT and using MinSatz is in some cases more efficient than reductions to SAT or Max-SAT. Since then many results connected to the Partial Min-SAT problem were published. However, to the best of our knowledge, the worst-case complexity of Partial Min-SAT has not been studied up until now. Our goal is to fix the issue and show a O*((2 - ε)m) lower bound under the SETH assumption (here m is the total number of clauses), as well as several other lower bounds and parameterized exact algorithms with better-than-trivial running time.
- Open Access
- 10 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (1) , 1-44
Tree Containment above Minimum Degree Is FPT
According to the classic Chvátal’s Lemma from 1977, a graph \( G \) of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \( n \) -vertex graph \( G \) , an integer \( k \) , and a tree \( T \) on at most \(\delta(G)+k\) vertices, deciding whether \( G \) contains a subgraph isomorphic to \( T \) can be done in time \(f(k)\cdot n^{\mathcal{O}(1)}\) for some function \( f \) of \( k \) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms.- 10 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (1) , 1-44
Open AccessTree Containment above Minimum Degree Is FPT
According to the classic Chvátal’s Lemma from 1977, a graph \( G \) of minimum degree \(\delta(G)\) contains every tree on \(\delta(G)+1\) vertices. Our main result is the following algorithmic “extension” of Chvátal’s Lemma: For any \( n \) -vertex graph \( G \) , an integer \( k \) , and a tree \( T \) on at most \(\delta(G)+k\) vertices, deciding whether \( G \) contains a subgraph isomorphic to \( T \) can be done in time \(f(k)\cdot n^{\mathcal{O}(1)}\) for some function \( f \) of \( k \) only. The proof is based on an intricate interplay between extremal graph theory and parameterized algorithms. - Open Access
Edge Clique Partition and Cover Beyond Independence
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 range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set α(G). Motivated by this observation, we investigate above αparameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/α) and Edge Clique Partition Above Independent Set (ECP/α), where the goal is to cover or partition all edges of a graph using at most α(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/αis fixed-parameter tractable, whereas ECC/αis NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/αbecomes fixed-parameter tractable when parameterized by k + ω(G), where ω(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which ωis typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.
Open AccessEdge Clique Partition and Cover Beyond Independence
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 range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set α(G). Motivated by this observation, we investigate above αparameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/α) and Edge Clique Partition Above Independent Set (ECP/α), where the goal is to cover or partition all edges of a graph using at most α(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/αis fixed-parameter tractable, whereas ECC/αis NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/αbecomes fixed-parameter tractable when parameterized by k + ω(G), where ω(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which ωis typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.
- Open Access
- 30 May 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (8) , 2676-2713
Approximating Long Cycle Above Dirac’s Guarantee
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than $$m/2 +k$$ clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least $$n/2 +k$$ for some $$k\ge 1$$ and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree $$\delta (G)\le n/2$$ , the length of a longest cycle L is at least $$2\delta (G)$$ . Thus the “essential” part in finding the longest cycle is in approximating the “offset” $$k = L - 2 \delta (G)$$ . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length $$2\delta (G)+\Omega (f(k))$$ .- 30 May 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (8) , 2676-2713
Open AccessApproximating Long Cycle Above Dirac’s Guarantee
Parameterization above (or below) a guarantee is a successful concept in parameterized algorithms. The idea is that many computational problems admit “natural” guarantees bringing to algorithmic questions whether a better solution (above the guarantee) could be obtained efficiently. For example, for every boolean CNF formula on m clauses, there is an assignment that satisfies at least m/2 clauses. How difficult is it to decide whether there is an assignment satisfying more than $$m/2 +k$$ clauses? Or, if an n-vertex graph has a perfect matching, then its vertex cover is at least n/2. Is there a vertex cover of size at least $$n/2 +k$$ for some $$k\ge 1$$ and how difficult is it to find such a vertex cover? The above guarantee paradigm has led to several exciting discoveries in the areas of parameterized algorithms and kernelization. We argue that this paradigm could bring forth fresh perspectives on well-studied problems in approximation algorithms. Our example is the longest cycle problem. One of the oldest results in extremal combinatorics is the celebrated Dirac’s theorem from 1952. Dirac’s theorem provides the following guarantee on the length of the longest cycle: for every 2-connected n-vertex graph G with minimum degree $$\delta (G)\le n/2$$ , the length of a longest cycle L is at least $$2\delta (G)$$ . Thus the “essential” part in finding the longest cycle is in approximating the “offset” $$k = L - 2 \delta (G)$$ . The main result of this paper is the above-guarantee approximation theorem for k. Informally, the theorem says that approximating the offset k is not harder than approximating the total length L of a cycle. In other words, for any (reasonably well-behaved) function f, a polynomial time algorithm constructing a cycle of length f(L) in an undirected graph with a cycle of length L, yields a polynomial time algorithm constructing a cycle of length $$2\delta (G)+\Omega (f(k))$$ . - Open Access
Algorithmic Extensions of Dirac's Theorem
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every $n$-vertex $2$-connected graph $G$ with minimum vertex degree $\delta\geq 2$ contains a cycle with at least $\min\{2\delta,n\}$ vertices. In particular, if $\delta\geq n/2$, then $G$ is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than $2\delta+1$. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least $n/2$. This prompts naturally to the following algorithmic questions. For $k\geq 1$, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least $\min\{2\delta+k,n\}$? (B) How difficult is to decide whether a graph $G$ is Hamiltonian, when at least $n - k$ vertices of $G$ are of degrees at least $n/2-k$? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of $k=1$, the existence of a polynomial-time algorithm deciding whether $G$ contains a cycle of length at least $\min\{2\delta+1,n\}$ was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but $k$ vertices of a $2$-connected graph $G$ are of degree at least $\delta$, then deciding whether $G$ has a cycle of length at least $\min\{2\delta +k, n\}$ can be done in time $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$. The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own.Open AccessAlgorithmic Extensions of Dirac's Theorem
In 1952, Dirac proved the following theorem about long cycles in graphs with large minimum vertex degrees: Every $n$-vertex $2$-connected graph $G$ with minimum vertex degree $\delta\geq 2$ contains a cycle with at least $\min\{2\delta,n\}$ vertices. In particular, if $\delta\geq n/2$, then $G$ is Hamiltonian. The proof of Dirac's theorem is constructive, and it yields an algorithm computing the corresponding cycle in polynomial time. The combinatorial bound of Dirac's theorem is tight in the following sense. There are 2-connected graphs that do not contain cycles of length more than $2\delta+1$. Also, there are non-Hamiltonian graphs with all vertices but one of degree at least $n/2$. This prompts naturally to the following algorithmic questions. For $k\geq 1$, (A) How difficult is to decide whether a 2-connected graph contains a cycle of length at least $\min\{2\delta+k,n\}$? (B) How difficult is to decide whether a graph $G$ is Hamiltonian, when at least $n - k$ vertices of $G$ are of degrees at least $n/2-k$? The first question was asked by Fomin, Golovach, Lokshtanov, Panolan, Saurabh, and Zehavi. The second question is due to Jansen, Kozma, and Nederlof. Even for a very special case of $k=1$, the existence of a polynomial-time algorithm deciding whether $G$ contains a cycle of length at least $\min\{2\delta+1,n\}$ was open. We resolve both questions by proving the following algorithmic generalization of Dirac's theorem: If all but $k$ vertices of a $2$-connected graph $G$ are of degree at least $\delta$, then deciding whether $G$ has a cycle of length at least $\min\{2\delta +k, n\}$ can be done in time $2^{\mathcal{O}(k)}\cdot n^{\mathcal{O}(1)}$. The proof of the algorithmic generalization of Dirac's theorem builds on new graph-theoretical results that are interesting on their own. - Open Access
- 15 March 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (6) , 2026-2040
Diverse Pairs of Matchings
We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$ -complete on general graphs ifkis part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$ parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$ vertices.- 15 March 2024
- Published by Springer Nature in Algorithmica
- Vol. 86 (6) , 2026-2040
Open AccessDiverse Pairs of Matchings
We initiate the study of theDiverse Pair of (Maximum/ Perfect) Matchingsproblems which given a graphGand an integerk, ask whetherGhas two (maximum/perfect) matchings whose symmetric difference is at leastk.Diverse Pair of Matchings(asking for two not necessarily maximum or perfect matchings) is $$\textsf{NP}$$ -complete on general graphs ifkis part of the input, and we consider two restricted variants. First, we show that on bipartite graphs, the problem is polynomial-time solvable, and second we show thatDiverse Pair of Maximum Matchingsis $$\textsf{FPT}$$ parameterized byk. We round off the work by showing thatDiverse Pair of Matchingshas a kernel on $${\mathcal {O}}(k^2)$$ vertices. - Open Access
Tree Containment Above Minimum Degree is FPT
According to the classic Chv{\'{a}}tal's Lemma from 1977, a graph of minimum degree $\delta(G)$ contains every tree on $\delta(G)+1$ vertices. Our main result is the following algorithmic "extension" of Chv\'{a}tal's Lemma: For any $n$-vertex graph $G$, integer $k$, and a tree $T$ on at most $\delta(G)+k$ vertices, deciding whether $G$ contains a subgraph isomorphic to $T$, can be done in time $f(k)\cdot n^{\mathcal{O}(1)}$ for some function $f$ of $k$ only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms.Open AccessTree Containment Above Minimum Degree is FPT
According to the classic Chv{\'{a}}tal's Lemma from 1977, a graph of minimum degree $\delta(G)$ contains every tree on $\delta(G)+1$ vertices. Our main result is the following algorithmic "extension" of Chv\'{a}tal's Lemma: For any $n$-vertex graph $G$, integer $k$, and a tree $T$ on at most $\delta(G)+k$ vertices, deciding whether $G$ contains a subgraph isomorphic to $T$, can be done in time $f(k)\cdot n^{\mathcal{O}(1)}$ for some function $f$ of $k$ only. The proof of our main result is based on an interplay between extremal graph theory and parameterized algorithms. - Open Access
Turán's Theorem Through Algorithmic Lens
The fundamental theorem of Turán from Extremal Graph Theory determines the exact bound on the number of edges $t_r(n)$ in an $n$-vertex graph that does not contain a clique of size $r+1$. We establish an interesting link between Extremal Graph Theory and Algorithms by providing a simple compression algorithm that in linear time reduces the problem of finding a clique of size $\ell$ in an $n$-vertex graph $G$ with $m \ge t_r(n)-k$ edges, where $\ell\leq r+1$, to the problem of finding a maximum clique in a graph on at most $5k$ vertices. This also gives us an algorithm deciding in time $2.49^{k}\cdot(n + m)$ whether $G$ has a clique of size $\ell$. As a byproduct of the new compression algorithm, we give an algorithm that in time $2^{\mathcal{O}(td^2)} \cdot n^2$ decides whether a graph contains an independent set of size at least $n/(d+1) + t$. Here $d$ is the average vertex degree of the graph $G$. The multivariate complexity analysis based on ETH indicates that the asymptotical dependence on several parameters in the running times of our algorithms is tight.Open AccessTurán's Theorem Through Algorithmic Lens
The fundamental theorem of Turán from Extremal Graph Theory determines the exact bound on the number of edges $t_r(n)$ in an $n$-vertex graph that does not contain a clique of size $r+1$. We establish an interesting link between Extremal Graph Theory and Algorithms by providing a simple compression algorithm that in linear time reduces the problem of finding a clique of size $\ell$ in an $n$-vertex graph $G$ with $m \ge t_r(n)-k$ edges, where $\ell\leq r+1$, to the problem of finding a maximum clique in a graph on at most $5k$ vertices. This also gives us an algorithm deciding in time $2.49^{k}\cdot(n + m)$ whether $G$ has a clique of size $\ell$. As a byproduct of the new compression algorithm, we give an algorithm that in time $2^{\mathcal{O}(td^2)} \cdot n^2$ decides whether a graph contains an independent set of size at least $n/(d+1) + t$. Here $d$ is the average vertex degree of the graph $G$. The multivariate complexity analysis based on ETH indicates that the asymptotical dependence on several parameters in the running times of our algorithms is tight.