Danil Sagunov

danilka.pro [at] gmail.com

Branching factor utility

[dblp] [rg] [scholar] [scopus] [orcid]

Danil Sagunov


I graduated from St. Petersburg Academic University and I was previously a PhD student in Steklov Institute of Mathematics at St. Petersburg (PDMI RAS) under supervision of Ivan Bliznets.

I also greatly appreciate working with a team of brilliant researchers Fedor V. Fomin, Petr A. Golovach and Kirill Simonov, whom I was happy to start communicating with on my very first research visit to the University of Bergen.

Research interests

parameterized complexity • algorithmic graph theory • exact algorithms • algorithms for NP-hard problems • kernelization • computational complexity • graph algorithms and parameters


  • Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov.
    Approximating Long Cycle Above Dirac's Guarantee
    ICALP 2023 [w]
    [LIPIcs] [arXiv]
  • Ivan Bliznets, Danil Sagunov, Kirill Simonov.
    Fine-grained Complexity of Partial Minimum Satisfiability
    IJCAI 2022
  • Ivan Bliznets, Anton Bukov, Danil Sagunov.
    Fair Division with Minimal Withheld Information in Social Networks
    COCOON 2022
  • Ivan Bliznets, Danil Sagunov.
    Two Generalizations of Proper Coloring: Hardness and Approximability
    COCOON 2022
  • Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov.
    Longest Cycle Above Erdős-Gallai Bound
    ESA 2022
    [LIPIcs] [arXiv]
  • Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Saket Saurabh, Kirill Simonov.
    Detours in Directed Graphs
    STACS 2022 [w]
    [arXiv] [LIPIcs]
  • Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, Kirill Simonov.
    Algorithmic Extensions of Dirac's Theorem
    SODA 2022 [w]
    [arXiv] [SIAM]
  • Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov.
    Diverse Pairs of Matchings
    ISAAC 2020 [w]
    [arXiv] [LIPIcs]
  • Fedor V. Fomin, Danil Sagunov, Kirill Simonov.
    Building large k-cores from sparse graphs
    MFCS 2020 [w]
    [arXiv] [LIPIcs]
  • Ivan Bliznets, Danil Sagunov.
    Maximizing Happiness in Graphs of Bounded Clique-Width
    LATIN 2020 [w]
    [arXiv] [LNCS]
  • Dmitry Itsykson, Artur Riazanov, Danil Sagunov, Petr Smirnov.
    Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
  • Ivan Bliznets, Danil Sagunov.
    Lower Bounds for the Happy Coloring Problems
    COCOON 2019 [w]
    [arXiv] [LNCS] [TCS]
  • Ivan Bliznets, Danil Sagunov.
    On Happy Colorings, Cuts, and Structural Parameterizations
    WG 2019 [w]
    [arXiv] [LNCS]
  • Ivan Bliznets, Danil Sagunov.
    Solving Target Set Selection with Bounded Thresholds Faster than 2^n
    IPEC 2018 [w]
    [arXiv] [LIPIcs]