Nemanja Draganic

FOCS Conference 2025 Conference Paper

Cycle-factors of regular graphs via entropy

• Micha Christoph
• Nemanja Draganic
• António Girão
• Eoin Hurley
• Lukas Michel
• Alp Müyesser

It is a classical result that a random permutation of n elements has, on average, about log n cycles. We generalise this fact to all directed d-regular graphs on n vertices by showing that, on average, a random cycle-factor of such a graph has $\mathcal{O}((n\log d)/d)$ cycles. This is tight up to the constant factor and improves the best previous bound of the form $\mathcal{O}(n/\sqrt {\log d} )$ due to Vishnoi. Our results also yield randomised polynomial-time algorithms for finding such a cycle-factor and for finding a tour of length $(1 + {\mathcal{O}}((\log d)/d)) \cdot n$ if the graph is connected. This makes progress on a conjecture of Magnant and Martin and on a problem studied by Vishnoi and by Feige, Ravi, and Singh. Our proof uses the language of entropy to exploit the fact that the upper and lower bounds on the number of perfect matchings in regular bipartite graphs are extremely close.

STOC Conference 2025 Conference Paper

Disjoint Connected Dominating Sets in Pseudorandom Graphs

• Nemanja Draganic
• Michael Krivelevich

A connected dominating set (CDS) in a graph is a dominating set of vertices that induces a connected subgraph. Having many disjoint CDSs in a graph can be considered as a measure of its connectivity, and has various graph-theoretic and algorithmic implications. We show that d -regular (weakly) pseudoreandom graphs contain (1+ o (1)) d /ln d disjoint CDSs, which is asymptotically best possible. In particular, this implies that random d -regular graphs typically contain (1+ o (1)) d /ln d disjoint CDSs.

SODA Conference 2024 Conference Paper

Edge-disjoint paths in expanders: online with removals

• Nemanja Draganic
• Rajko Nenadov

SODA Conference 2021 Conference Paper

Rolling backwards can move you forward: on embedding problems in sparse expanders

• Nemanja Draganic
• Michael Krivelevich
• Rajko Nenadov

We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanced with a roll-back idea allowing to sequentially retrace previously performed embedding steps. This proves to be a powerful tool for embedding graphs of large girth into expander graphs. As an application of this method, we settle two problems: • For a graph H, we denote by H q the graph obtained from H by subdividing its edges with q –1 vertices each. We show that the k -size-Ramsey number Ŗ k ( H q ) satisfies Ŗ k ( H q ) = O ( qn ) for every bounded degree graph H on n vertices and for q = Ω(log n ), which is optimal up to a constant factor. This settles a conjecture of Pak (2002). • We give a deterministic, polynomial time algorithm for finding vertex-disjoint paths between given pairs of vertices in a strong expander graph. More precisely, let G be an ( n, d, λ )-graph with λ = O ( d 1 – ∊ ), and let be any collection of at most disjoint pairs of vertices in G for some small constant c, such that in the neighborhood of every vertex in G there are at most d/ 4 vertices from. Then there exists a polynomial time algorithm which finds vertex-disjoint paths between every pair in, and each path is of the same length. Both the number of pairs and the length of the paths are optimal up to a constant factor; the result answers the offline version of a question of Alon and Capalbo (2007).