---
OA_place: repository
OA_type: green
_id: '21140'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Pavel
  full_name: Arkhipov, Pavel
  id: b25f2ab2-1fed-11ee-8599-fe02d211784f
  last_name: Arkhipov
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: 'Arkhipov P, Kolmogorov V. Faster algorithms for packing forests in graphs
    and related problems. In: <i>Proceedings of the 2026 Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>. Society for Industrial and Applied Mathematics; 2026:4023-4042.
    doi:<a href="https://doi.org/10.1137/1.9781611978971.148">10.1137/1.9781611978971.148</a>'
  apa: 'Arkhipov, P., &#38; Kolmogorov, V. (2026). Faster algorithms for packing forests
    in graphs and related problems. In <i>Proceedings of the 2026 Annual ACM-SIAM
    Symposium on Discrete Algorithms</i> (pp. 4023–4042). Vancouver, Canada: Society
    for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611978971.148">https://doi.org/10.1137/1.9781611978971.148</a>'
  chicago: Arkhipov, Pavel, and Vladimir Kolmogorov. “Faster Algorithms for Packing
    Forests in Graphs and Related Problems.” In <i>Proceedings of the 2026 Annual
    ACM-SIAM Symposium on Discrete Algorithms</i>, 4023–42. Society for Industrial
    and Applied Mathematics, 2026. <a href="https://doi.org/10.1137/1.9781611978971.148">https://doi.org/10.1137/1.9781611978971.148</a>.
  ieee: P. Arkhipov and V. Kolmogorov, “Faster algorithms for packing forests in graphs
    and related problems,” in <i>Proceedings of the 2026 Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, Vancouver, Canada, 2026, pp. 4023–4042.
  ista: 'Arkhipov P, Kolmogorov V. 2026. Faster algorithms for packing forests in
    graphs and related problems. Proceedings of the 2026 Annual ACM-SIAM Symposium
    on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 4023–4042.'
  mla: Arkhipov, Pavel, and Vladimir Kolmogorov. “Faster Algorithms for Packing Forests
    in Graphs and Related Problems.” <i>Proceedings of the 2026 Annual ACM-SIAM Symposium
    on Discrete Algorithms</i>, Society for Industrial and Applied Mathematics, 2026,
    pp. 4023–42, doi:<a href="https://doi.org/10.1137/1.9781611978971.148">10.1137/1.9781611978971.148</a>.
  short: P. Arkhipov, V. Kolmogorov, in:, Proceedings of the 2026 Annual ACM-SIAM
    Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
    2026, pp. 4023–4042.
conference:
  end_date: 2026-01-14
  location: Vancouver, Canada
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2026-01-11
corr_author: '1'
date_created: 2026-02-05T10:51:34Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-02-16T09:18:33Z
day: '07'
department:
- _id: VlKo
doi: 10.1137/1.9781611978971.148
external_id:
  arxiv:
  - '2409.20314'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2409.20314
month: '01'
oa: 1
oa_version: Preprint
page: 4023-4042
publication: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
  eisbn:
  - '9781611978971'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
status: public
title: Faster algorithms for packing forests in graphs and related problems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_type: closed access
_id: '18482'
abstract:
- lang: eng
  text: "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 ∈ \r\nRn. 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."
acknowledgement: The author is grateful to Maxim Balashov for setting the problem,
  providing useful literature, important discussions and text review. Also, I thank
  Dmitry Tsarev and Kseniia Petukhova for meaningful talks and support.
article_processing_charge: No
article_type: original
author:
- first_name: Pavel
  full_name: Arkhipov, Pavel
  id: b25f2ab2-1fed-11ee-8599-fe02d211784f
  last_name: Arkhipov
citation:
  ama: Arkhipov P. An algorithm for finding the generalized Chebyshev center of sets
    defined via their support functions. <i>Automation and Remote Control</i>. 2024;85(6):522-532.
    doi:<a href="https://doi.org/10.1134/S0005117924060031">10.1134/S0005117924060031</a>
  apa: Arkhipov, P. (2024). An algorithm for finding the generalized Chebyshev center
    of sets defined via their support functions. <i>Automation and Remote Control</i>.
    Springer Nature. <a href="https://doi.org/10.1134/S0005117924060031">https://doi.org/10.1134/S0005117924060031</a>
  chicago: Arkhipov, Pavel. “An Algorithm for Finding the Generalized Chebyshev Center
    of Sets Defined via Their Support Functions.” <i>Automation and Remote Control</i>.
    Springer Nature, 2024. <a href="https://doi.org/10.1134/S0005117924060031">https://doi.org/10.1134/S0005117924060031</a>.
  ieee: P. Arkhipov, “An algorithm for finding the generalized Chebyshev center of
    sets defined via their support functions,” <i>Automation and Remote Control</i>,
    vol. 85, no. 6. Springer Nature, pp. 522–532, 2024.
  ista: Arkhipov P. 2024. An algorithm for finding the generalized Chebyshev center
    of sets defined via their support functions. Automation and Remote Control. 85(6),
    522–532.
  mla: Arkhipov, Pavel. “An Algorithm for Finding the Generalized Chebyshev Center
    of Sets Defined via Their Support Functions.” <i>Automation and Remote Control</i>,
    vol. 85, no. 6, Springer Nature, 2024, pp. 522–32, doi:<a href="https://doi.org/10.1134/S0005117924060031">10.1134/S0005117924060031</a>.
  short: P. Arkhipov, Automation and Remote Control 85 (2024) 522–532.
corr_author: '1'
date_created: 2024-10-27T23:01:45Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2025-09-08T14:27:08Z
day: '01'
department:
- _id: GradSch
doi: 10.1134/S0005117924060031
external_id:
  isi:
  - '001338721700007'
intvolume: '        85'
isi: 1
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 522-532
publication: Automation and Remote Control
publication_identifier:
  eissn:
  - 1608-3032
  issn:
  - 0005-1179
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: An algorithm for finding the generalized Chebyshev center of sets defined via
  their support functions
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 85
year: '2024'
...
---
_id: '17136'
abstract:
- lang: eng
  text: "This paper focuses on Majority Dynamics in sparse graphs, in particular,
    as a\r\ntool to study internal cuts. It is known that, in Majority Dynamics on
    a finite\r\ngraph, each vertex eventually either comes to a fixed state, or oscillates
    with\r\nperiod two. The empirical evidence acquired by simulations suggests that
    for\r\nrandom odd-regular graphs, approximately half of the vertices end up\r\noscillating
    with high probability. We notice a local symmetry between\r\noscillating and non-oscillating
    vertices, that potentially can explain why the\r\nfraction of the oscillating
    vertices is concentrated around $\\frac{1}{2}$. In\r\nour simulations, we observe
    that the parts of random odd-regular graph under\r\nMajority Dynamics with high
    probability do not contain $\\lceil \\frac{d}{2}\r\n\\rceil$-cores at any timestep,
    and thus, one cannot use Majority Dynamics to\r\nprove that internal cuts exist
    in odd-regular graphs almost surely. However, we\r\nsuggest a modification of
    Majority Dynamics, that yields parts with desired\r\ncores with high probability."
acknowledgement: "I am grateful to Matthew Kwan for setting the problem, providing
  useful literature,\r\nfruitful discussions, text review, mentorship, general encouragement
  and support."
article_number: '2406.07026'
article_processing_charge: No
arxiv: 1
author:
- first_name: Pavel
  full_name: Arkhipov, Pavel
  id: b25f2ab2-1fed-11ee-8599-fe02d211784f
  last_name: Arkhipov
citation:
  ama: 'Arkhipov P. Majority dynamics and internal partitions of random regular graphs:
    Experimental results. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/arXiv.2406.07026">10.48550/arXiv.2406.07026</a>'
  apa: 'Arkhipov, P. (n.d.). Majority dynamics and internal partitions of random regular
    graphs: Experimental results. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.2406.07026">https://doi.org/10.48550/arXiv.2406.07026</a>'
  chicago: 'Arkhipov, Pavel. “Majority Dynamics and Internal Partitions of Random
    Regular Graphs: Experimental Results.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.2406.07026">https://doi.org/10.48550/arXiv.2406.07026</a>.'
  ieee: 'P. Arkhipov, “Majority dynamics and internal partitions of random regular
    graphs: Experimental results,” <i>arXiv</i>. .'
  ista: 'Arkhipov P. Majority dynamics and internal partitions of random regular graphs:
    Experimental results. arXiv, 2406.07026.'
  mla: 'Arkhipov, Pavel. “Majority Dynamics and Internal Partitions of Random Regular
    Graphs: Experimental Results.” <i>ArXiv</i>, 2406.07026, doi:<a href="https://doi.org/10.48550/arXiv.2406.07026">10.48550/arXiv.2406.07026</a>.'
  short: P. Arkhipov, ArXiv (n.d.).
date_created: 2024-06-12T07:01:52Z
date_published: 2024-06-11T00:00:00Z
date_updated: 2024-06-17T10:45:32Z
day: '11'
department:
- _id: GradSch
doi: 10.48550/arXiv.2406.07026
external_id:
  arxiv:
  - '2406.07026'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2406.07026
month: '06'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: 'Majority dynamics and internal partitions of random regular graphs: Experimental
  results'
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...