Source author record

Danil Sagunov

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computer Science and Game Theory Discrete Mathematics math.CO

Catalog footprint

Research overview

7works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

EFX and PO Allocation Exists for Two Types of 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 (Prakash HV et al. 2025) and for two types of goods (Gorantla, Marwaha, and Velusamy 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 quasiliniear time when there are two types of goods, given that the valuations are positive. This result strengthens the existing work of (Gorantla, Marwaha, and Velusamy 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.

preprint2026arXiv

Structural Approach to Guiding a Present-Biased Agent

Time-inconsistent behavior, such as procrastination or abandonment of long-term goals, arises when agents evaluate immediate outcomes disproportionately higher than future ones. This leads to globally suboptimal behavior, where plans are frequently revised or abandoned entirely. In the influential model of Kleinberg and Oren (2014) such behavior is modeled by a present-biased agent navigating a task graph toward a goal, making locally optimal decisions at each step based on discounted future costs. As a result, the agent may repeatedly deviate from initial plans. Recent work by Belova et al. (2024) introduced a two-agent extension of this model, where a fully-aware principal attempts to guide the present-biased agent through a specific set of critical tasks without causing abandonment. This captures a rich class of principal-agent dynamics in behavioral settings. In this paper, we provide a comprehensive algorithmic characterization of this problem. We analyze its computational complexity through the framework of parameterized algorithms, focusing on graph parameters that naturally emerge in this setting, such as treewidth, vertex cover, and feedback vertex set. Our main result is a fixed-parameter tractable algorithm when parameterized by the treewidth of the task graph and the number of distinct (v,t)-path costs. Our algorithm encaptures several input settings, such as bounded edge costs and restricted task graph structure. We demonstrate that our main result yields efficient algorithms for a number of such configurations. We complement this with tight hardness results, that highlight the extreme difficulty of the problem even on simplest graphs with bounded number of nodes and constant parameter values, and motivate our choice of parameters. We delineate tractable and intractable regions of the problem landscape, which include answers to open questions of Belova et al. (2024).

preprint2022arXiv

Detours in Directed Graphs

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 Path that we study, called Longest Detour, the task is to decide whether a graph has an (s,t)-path of length at least dist_G(s,t)+k (where dist_G(s,t) denotes the length of a shortest path from s to t). Bezáková et al. proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2^{O (k)} n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2^{O(k)} n^{O(1)} time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path Above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path Above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path Above Diameter is NP-complete even for k=1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path Above Diameter is solvable in polynomial time for each k\in{1,\dots, 4} and is NP-complete for every k\geq 5. The parameterized complexity of Longest Path Above Diameter on general directed graphs remains an interesting open problem.

preprint2022arXiv

Longest Cycle above Erdős-Gallai Bound

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 time 2^{O(k)} n^{O(1)} decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

preprint2020arXiv

Building large k-cores from sparse graphs

A popular model to measure network stability is the $k$ -core, that is the maximal induced subgraph in which every vertex has degree at least $k$ . For example, $k$ -cores are commonly used to model the unraveling phenomena in social networks. In this model, users having less than $k$ connections within the network leave it, so the remaining users form exactly the $k$ -core. In this paper we study the question whether it is possible to make the network more robust by spending only a limited amount of resources on new connections. A mathematical model for the $k$ -core construction problem is the following Edge $k$ -Core optimization problem. We are given a graph $G$ and integers $k$ , $b$ and $p$ . The task is to ensure that the $k$ -core of $G$ has at least $p$ vertices by adding at most $b$ edges. The previous studies on Edge $k$ -Core demonstrate that the problem is computationally challenging. In particular, it is NP-hard when $k=3$ , W[1]-hard being parameterized by $k+b+p$ (Chitnis and Talmon, 2018), and APX-hard (Zhou et al, 2019). Nevertheless, we show that there are efficient algorithms with provable guarantee when the $k$ -core has to be constructed from a sparse graph with some additional structural properties. Our results are 1) When the input graph is a forest, Edge $k$ -Core is solvable in polynomial time; 2) Edge $k$ -Core is fixed-parameter tractable (FPT) being parameterized by the minimum size of a vertex cover in the input graph. On the other hand, with such parameterization, the problem does not admit a polynomial kernel subject to a widely-believed assumption from complexity theory; 3) Edge $k$ -Core is FPT parameterized by $\mathrm{tw}+k$ . This improves upon a result of Chitnis and Talmon by not requiring $b$ to be small. Each of our algorithms is built upon a new graph-theoretical result interesting in its own.

preprint2020arXiv

Diverse Pairs of Matchings

We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph $G$ and an integer $k$ , ask whether $G$ has two (maximum/perfect) matchings whose symmetric difference is at least $k$ . Diverse Pair of Matchings (asking for two not necessarily maximum or perfect matchings) is NP-complete on general graphs if $k$ is 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 that Diverse Pair of Maximum Matchings is FPT parameterized by $k$ . We round off the work by showing that Diverse Pair of Matchings has a kernel on $\mathcal{O}(k^2)$ vertices.

preprint2020arXiv

Maximizing Happiness in Graphs of Bounded Clique-Width

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 we study how clique-width influences the complexity of the Maximum Happy Vertices (MHV) and Maximum Happy Edges (MHE) problems. We answer a question of Choudhari and Reddy '18 about parameterization by the distance to threshold graphs by showing that MHE is NP-complete on threshold graphs. Hence, it is not even in XP when parameterized by clique-width, since threshold graphs have clique-width at most two. As a complement for this result we provide a $n^{\mathcal{O}(\ell \cdot \operatorname{cw})}$ algorithm for MHE, where $\ell$ is the number of colors and $\operatorname{cw}$ is the clique-width of the input graph. We also construct an FPT algorithm for MHV with running time $\mathcal{O}^*((\ell+1)^{\mathcal{O}(\operatorname{cw})})$ , where $\ell$ is the number of colors in the input. Additionally, we show $\mathcal{O}(\ell n^2)$ algorithm for MHV on interval graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Danil Sagunov

Research overview

Is this your work?

7 publications

EFX and PO Allocation Exists for Two Types of Goods

Structural Approach to Guiding a Present-Biased Agent

Detours in Directed Graphs

Longest Cycle above Erdős-Gallai Bound

Building large k-cores from sparse graphs

Diverse Pairs of Matchings

Maximizing Happiness in Graphs of Bounded Clique-Width

See the researcher in context

Building this map preview