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