@inproceedings{21140,
  abstract     = {We consider several problems related to packing forests in graphs. The first one is to find k edge-disjoint forests in a directed graph G of maximal size such that the indegree of each vertex in these forests is at most k. We describe a min-max characterization for this problem and show that it can be solved in almost linear time for fixed k, extending the algorithm of [Gabow, 1995]. Specifically, the complexity is O(kδm log n), where n, m are the number of vertices and edges in G respectively, and δ = max{1, k − kG}, where kG is the edge connectivity of the graph. Using our solution to this problem, we improve complexities for two existing applications:(1) k-forest problem: find k forests in an undirected graph G maximizing the number of edges in their union. We show how to solve this problem in O(k3 min{kn, m} log2 n + k · MAXFLOW(m, m) log n) time, breaking the Ok(n3/2) complexity barrier of previously known approaches.(2) Directed edge-connectivity augmentation problem: find a smallest set of directed edges whose addition to the given directed graph makes it strongly k-connected. We improve the deterministic complexity for this problem from O(kδ(m + δn) log n) [Gabow, STOC 1994] to O(kδm log n). A similar approach with the same complexity also works for the undirected version of the problem.},
  author       = {Arkhipov, Pavel and Kolmogorov, Vladimir},
  booktitle    = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms},
  location     = {Vancouver, Canada},
  pages        = {4023--4042},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Faster algorithms for packing forests in graphs and related problems}},
  doi          = {10.1137/1.9781611978971.148},
  year         = {2026},
}

@unpublished{17136,
  abstract     = {This paper focuses on Majority Dynamics in sparse graphs, in particular, as a
tool to study internal cuts. It is known that, in Majority Dynamics on a finite
graph, each vertex eventually either comes to a fixed state, or oscillates with
period two. The empirical evidence acquired by simulations suggests that for
random odd-regular graphs, approximately half of the vertices end up
oscillating with high probability. We notice a local symmetry between
oscillating and non-oscillating vertices, that potentially can explain why the
fraction of the oscillating vertices is concentrated around $\frac{1}{2}$. In
our simulations, we observe that the parts of random odd-regular graph under
Majority Dynamics with high probability do not contain $\lceil \frac{d}{2}
\rceil$-cores at any timestep, and thus, one cannot use Majority Dynamics to
prove that internal cuts exist in odd-regular graphs almost surely. However, we
suggest a modification of Majority Dynamics, that yields parts with desired
cores with high probability.},
  author       = {Arkhipov, Pavel},
  booktitle    = {arXiv},
  title        = {{Majority dynamics and internal partitions of random regular graphs: Experimental results}},
  doi          = {10.48550/arXiv.2406.07026},
  year         = {2024},
}

@article{18482,
  abstract     = {This paper is dedicated to an optimization problem. Let A, B ⊂ Rn be compact convex sets. Consider the minimal number t0 > 0 such that t0B covers A after a shift to a vector x0 ∈ 
Rn. The goal is to find t0 and x0. In the special case of B being a unit ball centered at zero, x0 and t0 are known as the Chebyshev center and the Chebyshev radius of A. This paper focuses on the case in which A and B are defined with their black-box support functions. An algorithm for solving such problems efficiently is suggested. The algorithm has a superlinear convergence rate, and it can solve hundred-dimensional test problems in a reasonable time, but some additional conditions on A and B are required to guarantee the presence of convergence. Additionally, the behavior of the algorithm for a simple special case is investigated, which leads to a number of theoretical results. Perturbations of this special case are also studied.},
  author       = {Arkhipov, Pavel},
  issn         = {1608-3032},
  journal      = {Automation and Remote Control},
  number       = {6},
  pages        = {522--532},
  publisher    = {Springer Nature},
  title        = {{An algorithm for finding the generalized Chebyshev center of sets defined via their support functions}},
  doi          = {10.1134/S0005117924060031},
  volume       = {85},
  year         = {2024},
}