betaFeedback

WorksComputer Science

Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway Cut

Abstract

We give deterministic polynomial-time constructions of vertex multicut-mimicking networks of quasi-polynomial size. Given a graph G, a terminal set T, and a positive integer c, our algorithm constructs a graph with |T|^7 c^{O( log c ) } vertices that preserves every minimum vertex multiway cut value of at most c, for every partition of the terminals. Setting c=|T| gives an exact vertex multicut-mimicking network with |T|^{O( log |T| ) } vertices, resolving an open question of Wahlström [ACM Transactions on Algorithms 2022], who showed a bound of κ^{O( log^3 κ)} for the edge multicut-mimicking variant, where κ:= \sum_{t \in T} |N_G(t)| is the capacity of the terminal set, which was later improved to κ^{O( log^2 κ)} by Anand, Lee, Li and Saranurak [STOC 2024]. As applications of our vertex multicut-mimicking network, we obtain deterministic kernels of size k^{O( log k )} for Vertex Multiway Cut, p^{O(1)} k^{O(log k)} for Vertex Multicut with p requests and |Γ|^{O(1)} k^{O( log k)} for Group Feedback Vertex Set, where k is the deletion budget and Γis a finite group. Our first kernelization result, in particular, resolves an open question by Wahlström [ACM Transactions on Algorithms 2022], which was reiterated in a recent survey on kernelization by Jansen [Computer Science Reviews 2026]. Also, to the best of our knowledge, our kernel for Vertex Multicut is the first one whose size is completely polynomial in p and (quasi-polynomial) super-polynomial only in k. Finally, again using our vertex multicut-mimicking network for graphs, we obtain a hyperedge multicut-mimicking network for hypergraphs, which preserves hypergraph edge-multicuts of size up to c, of size |T|^{O(1)} c^{O(log c)}. Our result removes the dependence on the rank of the hypergraph from the exponent of the size bound, that existed in prior work.

Introduction

The computation of minimum cuts is fundamental to several algorithms for connectivity-based, graph partitioning and network design problems. When many minimum cut queries concern the same graph, compact representations can encode their answers without storing a separate solution for each query. For example, a Gomory-Hu tree represents a minimum ss-tt cut and its value for every pair of vertices s,t∈V(G)s,t \in V(G) using only ∣V(G)∣−1|V(G)| - 1 weighted edges [19].

Suppose now that the minimum cut queries involve only a designated set T⊆V(G)T \subseteq V(G) of terminals, but may ask to separate two arbitrary subsets of TT. That is, we are interested in compactly storing the value of a minimum XX-YY cut in a graph GG, for every possible X,Y⊆TX,Y \subseteq T. In this case the number of potential queries is exponential in ∣T∣|T|. Storing one minimum cut value for every choice of X,Y⊆TX,Y \subseteq T already gives a representation with exponential in ∣T∣|T| many entries (independent of the size of the graph). The interesting question here is whether the same information can be encoded in a much smaller graph containing TT, one whose size is sub-exponential, or quasi-polynomial or polynomial in ∣T∣|T|.

Cut sparsifiers and mimicking networks seek such representations preserving the relevant minimum cut values approximately or exactly. Given a graph GG and a designated set T⊆V(G)T \subseteq V(G) of terminals, a cut sparsifier is a smaller graph containing TT that approximately preserves minimum cut values between any two subsets of TT. The balance here is in the trade-off between its size and the approximation quality in guarantees [3, 44, 7, 37, 8, 42, 21, 39, 35, 38, 16, 13, 2, 34, 33, 24, 6, 32, 15]. When all minimum cut values (for two subsets of the terminal set) are preserved exactly, the replacement is called a mimicking network, a notion introduced by Hagerup, Katajainen, Nishimura, and Ragde [21] and widely studied thereafter [21, 34, 24, 33, 6, 42, 15].

The present work concerns mimicking networks for a more general family of cut queries. Let GG be a graph and T⊆V(G)T \subseteq V(G) be a set of kk terminals. We refer to (G,T)(G,T) as a terminal network. For a partition T={T1,…,Tt}\mathcal{T} = \{T_1,\ldots,T_t\} of TT, a vertex T\mathcal{T}-multiway cut (T\mathcal{T}-mwc) in GG is a set of vertices X⊆V(G)X \subseteq V(G) such that in G−XG-X, each connected component contains terminals from at most one part of T\mathcal{T}. A vertex multicut-mimicking network of (G,T)(G,T) is a graph G′G' with T⊆V(G′)T \subseteq V(G') such that for every T0⊆TT_0 \subseteq T and for every partition T\mathcal{T} of T∖T0T \setminus T_0, the size of a minimum T\mathcal{T}-mwc is identical in G−T0G-T_0 and in G′−T0G'-T_0. Note that when t=2t = 2, the resulting network is a mimicking network, thus multicut-mimicking networks are a generalization. In our setup, for the vertex deletion case, we allow the multiway cut solution to intersect the terminals TT, and we justify this assumption towards the end of this section2. The question we are investigating here is the following.

What is the minimum size ∣V(G′)∣|V(G')| for a vertex multicut-mimicking network, as a function of kk?3

In particular, can we bound ∣V(G′)∣|V(G')| (quasi-)polynomially in kk?

Further, can one also find such mimickers efficiently (in polynomial-time)?

This question is also motivated by the notorious open question of the existence of a polynomial kernel for Vertex Multiway Cut (see later), but is also interesting in its own right as a structural question in graph theory about compressing information about exponential behaviours in (quasi-)polynomial space: is there a graph on kO(1)k^{O(1)} or even kO(log⁡k)k^{O(\log k)} vertices that realizes the behaviour of a minimum multiway cut for each of the 2Θ(klog⁡k)2^{\Theta(k\log k)} partitions of TT?

When we omit the prefix vertex in front of multicut-mimicking network we refer to the one where the separators are edge cuts instead of vertex cuts. We also note that, generally, dealing with vertex cuts is much more challenging than dealing with edge cuts, in undirected graphs, and this happens to be the case also in our work. It is not difficult to observe that the existence and construction of vertex multicut-mimicking networks imply the same, with same bounds, for (edge) multicut-mimicking networks.

As a remark, one can also note that in the case of vertex multicut-mimicking networks we are preserving information about objects (T\mathcal{T}-mwc) that are NP-hard to compute even for one query [18], unlike mimicking networks, but still hoping for a construction that is both compact and computable in “purely” polynomial time, without assuming that the terminals or other parameters of the instance are constants. Below we describe the landscape of relevant results and how our results fit there. We also refer the reader to Table 1, Table 2 and Table 3 for comparison between known results and our results.

CutsTerminal partsApproximationConstructionSize
Edge21Deterministic22k2^{2^k} vertices [21]
—2Ω(k)2^{\Omega(k)} vertices necessary [34]
DeterministicO(k3)O(k^3) edges [31]
RandomizedO(kc3log⁡3/2(kc))O(kc^3\log^{3/2}(kc)) edges† [23]
O(log⁡klog⁡log⁡k)O\left(\frac{\log k}{\log\log k}\right)Deterministickk vertices [38]
Vertex21DeterministicO(k3)O(k^3) vertices [31, 30]
21Deterministick2O(c2)k^{2^{O(c^2)}} edges† [42]
m1+o(1)m^{1+o(1)}-time 2O(c2)2^{O(c^2)}
Edgess1DeterministicO(κs+1)O(\kappa^{s+1}) edges [31]
Unbounded2DeterministicO(κ3)O(\kappa^3) edges [45]
Unbounded1RandomizedκO(log⁡2κ)\kappa^{O(\log^2\kappa)} edges [45, 1]
Vertexss1DeterministicO(ks+1)O(k^{s+1}) vertices [31]
Unbounded2RandomizedO(k3)O(k^3) vertices [46]
Unbounded1Deterministick7cO(log⁡c)k^7c^{O(\log c)} vertices† Theorem 1.1
kO(log⁡k)k^{O(\log k)} vertices (Corollary 1.1)

Table 1. Graph sparsifiers and mimicking networks. Here k:=∣T∣k := |T|, and κ:=∑t∈Tdeg⁡G(t)\kappa:= \sum_{t\in T}\deg_G(t) denotes the terminal capacity. The rows indexed by ss preserve multiway cuts of terminal partitions into at most ss parts, for fixed ss. The construction column describes whether the algorithm is randomized or deterministic, and unless mentioned otherwise the time is purely polynomial. A dagger denotes connectivity-cc preservation, with cut values truncated at cc. The red row denotes our result. Blue construction labels denote results originally obtained by randomized algorithms whose constructions admit deterministic implementations using the cut-covering and representative-family machinery of Koana and Kumabe [30].

CutsTerminal PartsApproximationConstructionSize
Hyperedge21Randomized<br>O(kc3)O(kc^3) hyperedges† [23]<br>O(p1+o(1)+n(rclog⁡n)O(rc)log⁡m)O(p^{1+o(1)} + n(rc\log n)^{O(rc)}\log m)<br>RandomizedO(kc3log⁡3/2(2kc))O(kc^3\log^{3/2}(2kc)) hyperedges† [23]
HyperedgeUnbounded1Deterministic<br>p1+o(1)+k(crlog⁡n)O~(rc)mp^{1+o(1)} + k(cr\log n)^{\widetilde{O}(rc)}mkcO(rlog⁡c)kc^{O(r\log c)} hyperedges† [12]
HyperedgeUnbounded1DeterministickO(1)cO(log⁡c)k^{O(1)}c^{O(\log c)} encoding length†<br>(Theorem 1.2)
Weak vertexUnbounded1DeterministickO(1)cO(log⁡c)k^{O(1)}c^{O(\log c)} encoding length†<br>(Theorem 1.1, via clique hyperedges)
Strong vertex21–No computable vertex bound<br>(Appendix B)

Table 2. Hypergraph sparsifiers and mimicking networks. Here k:=∣T∣k := |T|, n:=∣V(H)∣n := |V(H)|, m:=∣E(H)∣m := |E(H)|, rr is the rank, and p:=∑e∈E(H)∣e∣p := \sum_{e\in E(H)} |e|. The construction column describes the whether the algorithm is randomized or deterministic, and unless mentioned otherwise the time is purely polynomial. A dagger denotes preservation after truncation at c+1c+1, normalizing threshold conventions across references. Red denotes this work. For strong deletion, unless FPT = W[2], no deterministic polynomial-time construction admits any computable vertex bound depending only on k,ck,c. This obstruction concerns unrestricted rank and already holds for one binary partition, with paid terminal deletion and no free terminal deletions.

DeletionProblemParameterConstructionSize
EdgeMultiway CutkkRandomizedkO(log⁡2k)k^{O(\log^2 k)} size [45, 1]
Vertexkk, fixed ttDeterministicO(kt+1)O(k^{t+1}) vertices [31, 30]
VertexkkDeterministickO(log⁡k)k^{O(\log k)} size<br>(Theorem 1.3)
EdgeMulticutk,pk,pRandomized(k+p)O(log⁡2(k+p))(k+p)^{O(\log^2(k+p))} size [45, 1]
Vertexkk, fixed ppDeterministicO(k⌈2p⌉+1)O(k^{\lceil\sqrt{2p}\rceil+1}) vertices [31, 30]
Vertexk,pk,pDeterministicpO(1)kO(log⁡k)p^{O(1)}k^{O(\log k)} size<br>(Theorem 1.4)
EdgeGroup Feedback Setk,∣Γ∣k,|\Gamma|Randomized∣Γ∣O(1)kO(log⁡2k)|\Gamma|^{O(1)}k^{O(\log^2 k)} size [45, 1]
Vertexkk, fixed Γ\GammaDeterministicO((klog⁡klog⁡log⁡k)∣Γ∣+1)O((k\log k\log\log k)^{|\Gamma|+1}) vertices [31, 30]
Vertexk,∣Γ∣k,|\Gamma|Deterministic∣Γ∣O(1)kO(log⁡k)|\Gamma|^{O(1)}k^{O(\log k)} encoding length<br>(Theorem 1.5)

Table 3. Kernelization results for edge and vertex deletion. Here kk is the deletion budget, tt is the number of Multiway Cut terminals and pp is the number of Multicut requests. Terminals are undeletable in the vertex cut problems. All constructions take polynomial time, with the quantities explicitly marked fixed held constant. In the uniform group-feedback rows, Γ\Gamma is supplied by its multiplication table. Blue denotes deterministic consequences of the representative-family machinery of Koana and Kumabe [30]. Red denotes this work.

Mimicking networks and cut sparsifiers. For exact minimum edge-cut preservation, the size of a mimicking network can be exponential in the number of terminals. Hagerup, Katajainen, Nishimura, and Ragde [21] showed that every edge-weighted graph with kk terminals admits a mimicking network with at most 22k2^{2^k} vertices. Krauthgamer and Rika [34] proved that 2Ω(k)2^{\Omega(k)} vertices are necessary for some terminal networks.

Allowing to only preserve approximations of a minimum cut for every query, give a spectrum of different tradeoffs between the size of the mimicking network and its quality. We do not go deep into surveying this literature here. Moitra [39] studied cut sparsifiers whose vertex set consists only of the terminals. Such sparsifiers of quality O(log⁡k/log⁡log⁡k)O(\log k/\log\log k) exist and can be constructed in polynomial time [38, 16].

References

  1. [1]A. Anand, E. Lee, J. Li, and T. Saranurak, Approximating small sparse cuts, in Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, B. Mohar, I. Shinkar, and R. O’Donnell, eds., ACM, 2024, pp. 319–330.arxiv.org/abs/2403.08983
  2. [2]A. Andoni, A. Gupta, and R. Krauthgamer, Towards (1 + ε)-approximate flow sparsifiers, in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, C. Chekuri, ed., SIAM, 2014, pp. 279–293.arxiv.org/abs/1310.3252
  3. [3]A. A. Benczúr and D. R. Karger, Randomized approximation schemes for cuts and flows in capacitated graphs, SIAM J. Comput., 44 (2015), pp. 290–319.
  4. [4]J. Brakensiek and V. Guruswami, Redundancy is all you need, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, M. Koucký and N. Bansal, eds., ACM, 2025, pp. 1614–1625.DOI
  5. [5]J. Brakensiek, V. Guruswami, and A. Putterman, Multiplicative error set system sparsification: A simpler proof via chain length contraction, in 53rd International Colloquium on Automata, Languages, and Programming, ICALP 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026, S. Bhattacharya, D. Nanongkai, M. Benedikt, and G. Puppis, eds., vol. 374 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, pp. 44:1–44:17.
  6. [6]P. Chalermsook, S. Das, Y. Kook, B. Laekhanukit, Y. P. Liu, R. Peng, M. Sellke, and D. Vaz, Vertex sparsification for edge connectivity, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, D. Marx, ed., SIAM, 2021, pp. 1206–1225.arxiv.org/abs/2007.07862
  7. [7]L. Chen, G. Goranci, M. Henzinger, R. Peng, and T. Saranurak, Fast dynamic cuts, distances and effective resistances via vertex sparsifiers, in 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, S. Irani, ed., IEEE, 2020, pp. 1135–1146.arxiv.org/abs/2005.02368
  8. [8]L. Chen, R. Kyng, Y. P. Liu, R. Peng, M. P. Gutenberg, and S. Sachdeva, Maximum flow and minimum-cost flow in almost-linear time, J. ACM, 72 (2025), pp. 19:1–19:103.
  9. [9]Y. Chen, S. Khanna, and A. Nagda, Near-linear size hypergraph cut sparsifiers, in 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, S. Irani, ed., IEEE, 2020, pp. 61–72.arxiv.org/abs/2009.04992
  10. [10]Y. Chen and Z. Tan, On (1 + ε)-approximate flow sparsifiers, in Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, D. P. Woodruff, ed., SIAM, 2024, pp. 1568–1605.
  11. [11]Y. Chen, Z. Tan, and M. Yang, Lower bounds on flow sparsifiers with steiner nodes, in Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, Salt Lake City, UT, USA, June 22-26, 2026, A. Bhaskara and A. Czumaj, eds., ACM, 2026, pp. 1365–1375.
  12. [12]K. Cho and E. Oh, Mimicking networks for constrained multicuts in hypergraphs, in 35th International Symposium on Algorithms and Computation, ISAAC 2024, Sydney, Australia, December 8-11, 2024, J. Mestre and A. Wirth, eds., vol. 322 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, pp. 21:1–21:14.arxiv.org/abs/2409.12548
  13. [13]J. Chuzhoy, On vertex sparsifiers with Steiner nodes, in Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, H. J. Karloff and T. Pitassi, eds., ACM, 2012, pp. 673–688.arxiv.org/abs/1204.2844
  14. [14]M. Cygan, M. Pilipczuk, and M. Pilipczuk, On group feedback vertex set parameterized by the size of the cutset, Algorithmica, 74 (2016), pp. 630–642.
  15. [15]S. Das, N. Kumar, and D. Vaz, Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs, in 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, Bratislava, Slovakia, August 26-30, 2024, R. Královic and A. Kucera, eds., vol. 306 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, pp. 45:1–45:17.DOI
  16. [16]M. Englert, A. Gupta, R. Krauthgamer, H. Räcke, I. Talgam-Cohen, and K. Talwar, Vertex sparsifiers: New results from old techniques, SIAM J. Comput., 43 (2014), pp. 1239–1262.
  17. [17]F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi, Kernelization: theory of parameterized preprocessing, Cambridge University Press, 2019.
  18. [18]N. Garg, V. V. Vazirani, and M. Yannakakis, Multiway cuts in directed and node weighted graphs, in Automata, Languages and Programming (ICALP), vol. 820 of Lecture Notes in Computer Science, Springer, 1994, pp. 487–498.DOI
  19. [19]R. E. Gomory and T. C. Hu, Multi-terminal network flows, Journal of the Society for Industrial and Applied Mathematics, 9 (1961), pp. 551–570.DOI
  20. [20]S. GuillemoT, FPT algorithms for path-transversal and cycle-transversal problems, Discret. Optim., 8 (2011), pp. 61–71.DOI
  21. [21]T. Hagerup, J. Katajainen, N. Nishimura, and P. Ragde, Characterizing multiterminal flow networks and computing flows in networks of small treewidth, J. Comput. Syst. Sci., 57 (1998), pp. 366–375.DOI
  22. [22]B. M. P. Jansen, Quo vadis, kernelization?, Comput. Sci. Rev., 62 (2026), p. 101035.DOI
  23. [23]H. Jiang, S. Huang, T. Saranurak, and T. Zhang, Vertex sparsifiers for hyperedge connectivity, in 30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022, S. Chechik, G. Navarro, E. Rotenberg, and G. Herman, eds., vol. 244 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 70:1–70:13.arxiv.org/abs/2207.04115
  24. [24]N. Karpov, M. Pilipczuk, and A. Zych-Pawlewicz, An exponential lower bound for cut sparsifiers in planar graphs, Algorithmica, 81 (2019), pp. 4029–4042.arxiv.org/abs/1706.06086
  25. [25]A. Khan and P. Raghavendra, On mimicking networks representing minimum terminal cuts, Inf. Process. Lett., 114 (2014), pp. 365–371.arxiv.org/abs/1207.6371
  26. [26]S. Khanna, A. Putterman, and M. Sudan, Near-optimal size linear sketches for hypergraph cut sparsifiers, in 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, IEEE, 2024, pp. 1669–1706.arxiv.org/abs/2407.03934
  27. [27]——, Efficient algorithms and new characterizations for CSP sparsification, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, M. Koucký and N. Bansal, eds., ACM, 2025, pp. 407–416.arxiv.org/abs/2404.06327
  28. [28]——, A theory of spectral CSP sparsification, in 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, K. Censor-Hillel, F. Grandoni, J. Ouaknine, and G. Puppis, eds., vol. 334 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, pp. 107:1–107:12.arxiv.org/abs/2504.16206
  29. [29]S. Khanna, A. L. Putterman, and M. Sudan, Code sparsification and its applications, in Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, D. P. Woodruff, ed., SIAM, 2024, pp. 5145–5168.arxiv.org/abs/2311.00788
  30. [30]T. Koana and S. Kumabe, A deterministic polynomial kernel for odd cycle transversal, CoRR, abs/2609.29141 (2026).arxiv.org/abs/2609.29141
  31. [31]S. Kratsch and M. Wahlström, Representative sets and irrelevant vertices: New tools for kernelization, J. ACM, 67 (2020), pp. 16:1–16:50.
  32. [32]R. Krauthgamer and R. Mosenzon, Exact flow sparsification requires unbounded size, in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023, N. Bansal and V. Nagarajan, eds., SIAM, 2023, pp. 2354–2367.arxiv.org/abs/2207.07363
  33. [33]R. Krauthgamer and H. Rika, Refined vertex sparsifiers of planar graphs, SIAM J. Discret. Math., 34 (2020), pp. 101–129.arxiv.org/abs/1702.05951
  34. [34]R. Krauthgamer and I. Rika, Mimicking networks and succinct representations of terminal cuts, in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, S. Khanna, ed., SIAM, 2013, pp. 1789–1799.
  35. [35]F. T. Leighton and A. Moitra, Extensions and limits to vertex sparsification, in Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, L. J. Schulman, ed., ACM, 2010, pp. 47–56.DOI
  36. [36]Y. P. Liu, Vertex sparsification for edge connectivity in polynomial time, in 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023, Y. T. Kalai, ed., vol. 251 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 83:1–83:15.
  37. [37]A. Madry, Fast approximation algorithms for cut-based problems in undirected graphs, in 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, October 23-26, 2010, IEEE Computer Society, 2010, pp. 245–254.arxiv.org/abs/1008.1975
  38. [38]K. Makarychev and Y. Makarychev, Metric extension operators, vertex sparsifiers and Lipschitz extendability, in 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, October 23-26, 2010, IEEE Computer Society, 2010, pp. 255–264.
  39. [39]A. Moitra, Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size, in 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, Atlanta, Georgia, USA, October 25-27, 2009, IEEE Computer Society, 2009, pp. 3–12.DOI
  40. [40]——, Vertex sparsification and oblivious reductions, SIAM J. Comput., 42 (2013), pp. 2400–2423.DOI
  41. [41]J. Oxley, Matroid Theory, Oxford University Press, 2011.
  42. [42]T. Saranurak and S. Yingchareonthawornchai, Deterministic small vertex connectivity in almost linear time, in 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, IEEE, 2022, pp. 789–800.arxiv.org/abs/2210.13739
  43. [43]A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and combinatorics, Springer, 2003.
  44. [44]D. A. Spielman and S. Teng, Spectral sparsification of graphs, SIAM J. Comput., 40 (2011), pp. 981–1025.
  45. [45]M. Wahlström, Quasipolynomial multicut-mimicking networks and kernels for multiway cut problems, ACM Trans. Algorithms, 18 (2022), pp. 15:1–15:19.DOI
  46. [46]——, Representative set statements for delta-matroids and the mader delta-matroid, in Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, D. P. Woodruff, ed., SIAM, 2024, pp. 780–810.arxiv.org/abs/2306.03605

Paper details

vlnc:W_2nv5udg3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents