[{"day":"07","conference":{"name":"SODA: Symposium on Discrete Algorithms","start_date":"2026-01-11","location":"Vancouver, Canada","end_date":"2026-01-14"},"publisher":"Society for Industrial and Applied Mathematics","department":[{"_id":"VlKo"}],"publication":"Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms","publication_status":"published","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","quality_controlled":"1","fulldoi":"https://doi.org/10.1137/1.9781611978971.148","month":"01","oa_version":"Preprint","article_processing_charge":"No","author":[{"id":"b25f2ab2-1fed-11ee-8599-fe02d211784f","last_name":"Arkhipov","full_name":"Arkhipov, Pavel","first_name":"Pavel"},{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov"}],"date_created":"2026-02-05T10:51:34Z","page":"4023-4042","corr_author":"1","external_id":{"arxiv":["2409.20314"]},"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."}],"oa":1,"title":"Faster algorithms for packing forests in graphs and related problems","publication_identifier":{"eisbn":["9781611978971"]},"OA_place":"repository","OA_type":"green","date_updated":"2026-02-16T09:18:33Z","status":"public","type":"conference","date_published":"2026-01-07T00:00:00Z","doi":"10.1137/1.9781611978971.148","_id":"21140","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2409.20314","open_access":"1"}],"arxiv":1,"citation":{"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.","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.","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.","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>","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>.","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>","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>."},"year":"2026"},{"title":"Majority dynamics and internal partitions of random regular graphs: Experimental results","oa":1,"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."}],"external_id":{"arxiv":["2406.07026"]},"_id":"17136","date_published":"2024-06-11T00:00:00Z","doi":"10.48550/arXiv.2406.07026","type":"preprint","status":"public","date_updated":"2026-10-02T11:06:38Z","article_number":"2406.07026","das_tickbox":"0","citation":{"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>.","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>","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>.","short":"P. Arkhipov, ArXiv (n.d.).","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.","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>"},"researchdata_availability":"yes","arxiv":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2406.07026","open_access":"1"}],"year":"2024","acknowledgement":"I am grateful to Matthew Kwan for setting the problem, providing useful literature,\r\nfruitful discussions, text review, mentorship, general encouragement and support.","day":"11","department":[{"_id":"GradSch"}],"language":[{"iso":"eng"}],"publication_status":"submitted","publication":"arXiv","article_processing_charge":"No","oa_version":"Preprint","month":"06","supplementarymaterial":"no","fulldoi":"https://doi.org/10.48550/arXiv.2406.07026","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2024-06-12T07:01:52Z","author":[{"last_name":"Arkhipov","id":"b25f2ab2-1fed-11ee-8599-fe02d211784f","first_name":"Pavel","full_name":"Arkhipov, Pavel"}]},{"volume":85,"issue":"6","_id":"18482","date_published":"2024-06-01T00:00:00Z","doi":"10.1134/S0005117924060031","status":"public","type":"journal_article","date_updated":"2026-10-02T11:10:45Z","abstract":[{"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.","lang":"eng"}],"external_id":{"isi":["001338721700007"]},"OA_type":"closed access","title":"An algorithm for finding the generalized Chebyshev center of sets defined via their support functions","publication_identifier":{"eissn":["1608-3032"],"issn":["0005-1179"]},"year":"2024","citation":{"short":"P. Arkhipov, Automation and Remote Control 85 (2024) 522–532.","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.","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>","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>.","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>","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>."},"researchdata_availability":"no","intvolume":"        85","das_tickbox":"0","publication":"Automation and Remote Control","language":[{"iso":"eng"}],"publication_status":"published","article_type":"original","day":"01","publisher":"Springer Nature","department":[{"_id":"GradSch"}],"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.","isi":1,"scopus_import":"1","author":[{"full_name":"Arkhipov, Pavel","first_name":"Pavel","last_name":"Arkhipov","id":"b25f2ab2-1fed-11ee-8599-fe02d211784f"}],"corr_author":"1","date_created":"2024-10-27T23:01:45Z","page":"522-532","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","article_processing_charge":"No","oa_version":"None","supplementarymaterial":"no","fulldoi":"https://doi.org/10.1134/S0005117924060031","quality_controlled":"1","month":"06"}]