Arrow Research search

Author name cluster

Parinya Chalermsook

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers
1 author row

Possible papers

17

SODA Conference 2023 Conference Paper

Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition

  • Parinya Chalermsook
  • Manoj Gupta 0002
  • Wanchote Jiamjitrak
  • Nidia Obscura Acosta
  • Akash Pareek
  • Sorrachai Yingchareonthawornchai

Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i. e. , starting with any initial tree, their access costs on any sequence is conjectured to be within O (1) factor of the offline optimal. However, despite having received a lot of attention in the past four decades, the question has remained elusive even for highly restricted input. In this paper, we prove new bounds on the cost of Greedy in the “pattern avoidance” regime. Our new results include: • The (preorder) traversal conjecture for Greedy holds up to a factor of O (2 α( n ) ), improving upon the bound of 2 α( n ) O (1) in (Chalermsook et al. , FOCS 2015) where α(n) is the inverse Ackermann function of n. This is the best known bound obtained by any online BSTs. • We settle the postorder traversal conjecture for Greedy. Previously this was shown for Splay trees only in certain special cases (Levy and Tarjan, WADS 2019). • The deque conjecture for Greedy holds up to a factor of O (α( n )), improving upon the bound 2 O(α(n)) in (Chalermsook, et al. , WADS 2015). This is arguably “one step away” from the bound O(α * (n)) for Splay trees (Pettie, SODA 2010). • The split conjecture holds for Greedy up to a factor of O(2 α(n) ). Previously the factor of O(α(n)) was shown for Splay trees only in a special case (Lucas, 1988). The input sequences in traversal and deque conjectures are perhaps “easiest” in the pattern-avoiding input classes and yet among the most notorious special cases of the dynamic optimality conjecture. Key to all these results is to partition (based on the input structures) the execution log of Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be leveraged. We believe that this simple method will find further applications in doing amortized analysis of data structures via extremal combinatorics. Finally, we show the applicability of this technique to handle a class of increasingly complex pattern-avoiding input sequences, called k-increasing sequences. As a bonus, we discover a new class of permutation matrices whose extremal bounds are polynomially bounded. This gives a partial progress on an open question by Jacob Fox (2013). * The full version of the paper can be accessed at https: //arxiv. org/abs/2211. 04112

Details

FOCS Conference 2023 Conference Paper

Parameterized Approximation Schemes for Clustering with General Norm Objectives

  • Fateme Abbasi
  • Sandip Banerjee
  • Jaroslaw Byrka
  • Parinya Chalermsook
  • Ameet Gadekar
  • Kamyar Khodamoradi
  • Dániel Marx
  • Roohani Sharma

This paper considers the well-studied algorithmic regime of designing a $(1+\epsilon)$-approximation algorithm for a k-clustering problem that runs in time $f(k, \epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short 1 ). Notable results of this kind include EPASes in the high-dimensional Euclidean setting for k-center [Badŏiu, Har-Peled, Indyk; STOC’02] as well as k-median, and k-means [Kumar, Sabharwal, Sen; J. ACM 2010]. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple well-studied objectives as well as metric spaces) and unifies well-known EPASes. More specifically, our algorithm gives EPASes in the following settings: •Clustering objectives: k-means, k-center, k-median, priority k-center, $\ell$-centrum, ordered k-median, socially fair k-median (aka robust k-median), or any other objective that can be formulated as minimizing a monotone (not necessarily symmetric!) norm of the distances of the points from the solution (generalizing the symmetric formulation introduced by Chakrabarty and Swamy [STOC’19]). •Metric spaces: Continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics. Prior to our results, EPASes were only known for vanilla clustering objectives (k-means, k-median, and k-center) and each such algorithm is tailored to work for the specific input metric and clustering objective (e. g. , EPASes for k means and k-center in $\mathbb{R}^{d}$ are conceptually very different). In contrast, our algorithmic framework is applicable to a wide range of well-studied objective functions in a uniform way, and is (almost) entirely oblivious to any specific metric structures and yet is able to effectively exploit those unknown structures. In particular, our algorithm is not based on the (metric- and objective-specific) technique of coresets. Key to our analysis is a new concept that we call bounded $\epsilon$-scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension(often used as a source of algorithmic tractability for geometric problems). Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric M for any clustering objective: (i)The objective is described by a monotone norm, and(ii)the $\epsilon$-scatter dimension of M is upper bounded by a function of $\epsilon$. 1 Quick remarks: (i) An EPAS is not comparable to polynomial time approximation schemes (PTAS), (ii) before the term EPAS was invented some researchers call this type of approximation schemes a PTAS or simply an approximation scheme (in clustering, it is often assumed that k is small) [1], [2], and (iii) both EPAS and PTAS are implied by the existence of efficient polynomial time approximation schemes (EPTAS).

Details

SODA Conference 2021 Conference Paper

Coloring and Maximum Weight Independent Set of Rectangles

  • Parinya Chalermsook
  • Bartosz Walczak

In 1960, Asplund and Grünbaum proved that every intersection graph of axis-parallel rectangles in the plane admits an O ( ω 2 )-coloring, where ω is the maximum size of a clique. We present the first asymptotic improvement over this six-decade-old bound, proving that every such graph is O ( ω log ω )-colorable and presenting a polynomial-time algorithm that finds such a coloring. This improvement leads to a polynomial-time O (log log n )-approximation algorithm for the maximum weight independent set problem in axis-parallel rectangles, which improves on the previous approximation ratio of.

Details

SODA Conference 2021 Conference Paper

Vertex Sparsification for Edge Connectivity

  • Parinya Chalermsook
  • Syamantak Das
  • Yunbum Kook
  • Bundit Laekhanukit
  • Yang P. Liu
  • Richard Peng
  • Mark Sellke
  • Daniel Vaz 0001

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether (1 + ∊ )-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thresholded version of the problem: for a given parameter c, find a smaller graph, which we call connectivity-c mimicking network, which preserves connectivity among k terminals exactly up to the value of c. We show that connectivity- c mimicking networks with O ( kc 4 ) edges exist and can be found in time m ( c log n ) O ( c ). We also give a separate algorithm that constructs such graphs with k · O ( c ) 2 c edges in time mc O ( c ) log O (1) n. These results lead to the first data structures for answering fully dynamic offline c -edge-connectivity queries for c ≥ 4 in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.

Details

SODA Conference 2017 Conference Paper

Beyond Metric Embedding: Approximating Group Steiner Trees on Bounded Treewidth Graphs

  • Parinya Chalermsook
  • Syamantak Das
  • Bundit Laekhanukit
  • Daniel Vaz 0001

The Group Steiner Tree (GST) problem is a classical problem in combinatorial optimization and theoretical computer science. In the Edge-Weighted Group Steiner Tree (EW-GST) problem, we are given an undirected graph G = ( V, E ) on n vertices with edge costs c: E → ℝ≥ 0, a source vertex s and a collection of subsets of vertices, called groups, S 1, …, S k ⊆ V. The goal is to find a minimum-cost tree H ⊆ G that connects s to some vertex from each group S i, for all i = 1, 2, …, k. The Node-Weighted Group Steiner Tree (NW-GST) problem has the same setting, but the costs are associated with nodes. The goal is to find a minimum- cost node set X ⊆ V such that G[X ] connects every group to the source. When G is a tree, both EW-GST and NW-GST admit a polynomial-time O (log n log k ) approximation algorithm due to the seminal result of [Garg et al. , SODA'98 and J. Algorithm]. The matching hardness of log 2 −∊ n is known even for tree instances of EW-GST and NW-GST [Halperin and Krauthgamer STOC'03]. In general graphs, most of polynomial-time approximation algorithms for EW- GST reduce the problem to a tree instance using the metric- tree embedding, incurring a loss of O (log n ) on the approximation factor [Bartal, FOCS'96; Fakcharoenphol et al. , FOCS'03 and JCSS]. This yields an approximation ratio of O (log n log k ) for EW-GST. Using metric-tree embedding, this factor cannot be improved: The loss of O (log n ) is necessary on some input graphs (e. g. , grids and expanders). There are alternative approaches that avoid metric-tree embedding, e. g. , the algorithm of [Chekuri and Pal, FOCS'05], which gives a tight approximation ratio, but none of which achieves polylogarithmic approximation in polynomial-time. This state of the art shows a clear lack of understanding of GST in general graphs beyond the metric-tree embedding technique. For NW-GST (for which the metric-tree embedding does not apply), not even a polynomial-time polyloga- rithmic approximation algorithm is known. In this paper, we present O (log n log k ) approximation algorithms that run in time n Õ ( tw(G )2 ‘for both NW-GST and EW-GST 1, where tw(G) denotes the treewidth of graph G. The key to both results is a different type of “tree- embedding” that produces a tree of much bigger size, but does not cause any loss on the approximation factor. Our embedding is inspired by dynamic programming, a technique which is typically not applicable to Group Steiner problems.

Details

FOCS Conference 2017 Conference Paper

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

  • Parinya Chalermsook
  • Marek Cygan
  • Guy Kortsarz
  • Bundit Laekhanukit
  • Pasin Manurangsi
  • Danupon Nanongkai
  • Luca Trevisan 0001

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e. g. , [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i. e. , there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e. g. , this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (GapETH) [4], [5], which states that no 2 o(n) -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e. g. , Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k o(1) -FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log 1/4+ε (OPT) approximation for DomSet for any constant ε > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

Details

SODA Conference 2015 Conference Paper

On Survivable Set Connectivity

  • Parinya Chalermsook
  • Fabrizio Grandoni 0001
  • Bundit Laekhanukit

In the Set Connectivity problem, we are given an n -node edge-weighted undirected graph and a collection of h set pairs ( S i, T i ), where S i and T i are subsets of nodes. The goal is to compute a min-cost subgraph H so that, for each set pair ( S i, T i ), there exists at least one path in H between some node in S i and some node in T i. In this paper, we initiate the study of the Survivable Set Connectivity problem (SSC), i. e. , the generalization of Set Connectivity where we are additionally given an integer requirement k i ≥ 1 for each set pair ( S i, T i ), and we want to find a min-cost subgraph H so that there are at least k i edge-disjoint paths in H between S i and T i. We achieve the following main results: • We show that there is no poly-logarithmic approximation for SSC unless NP has a quasi-polynomial time algorithm. This result is based on a reduction from the Minimum Label Cover problem, and the result holds even for the special case where S i = { r } for all i, i. e. , for the high-connectivity variant of the classical Group Steiner Tree problem. More precisely, we prove an approximability lower bound of 2 log1−ε n for SSC, for any constant ∊ > 0, which is almost polynomial on n. A technical novelty of our proof is the first use of a padding scheme technique for an edge-connectivity problem on undirected graphs. (Prior to our results, the applications of this technique only pertain to either node-connectivity problems or problems on directed graphs). • We present a bicriteria approximation algorithm for SSC that computes a solution H of cost at most poly-logarithmically larger than the optimal cost and provides a connectivity at least Ω ( k i /log n ) for each set pair ( S i, T i ). The main algorithmic idea is to solve a standard LP relaxation to the problem, and then embed the resulting fractional capacities into a tree via Räcke's cut-based tree embeddings. Based on that, we generate a random collection of Group Steiner Tree-like fractional solutions, which can then be handled by the rounding scheme of [Garg, Konjevod and Ravi – SODA'98]. The prior work on Set Connectivity and Group Steiner Tree used Bartal's distance-based tree embeddings which do not seem to generalize to the k -connectivity versions of these problems. Finally, we remark an interesting contrast demonstrated by our results: While our hardness result almost rules out “polynomial” approximation ratios, relaxing connectivity constraints allows us to obtain “poly-logarithmic” bounds. This naturally suggests that relaxing connectivity requirements might be a proper way in getting big improvements, even beyond (non-bicriteria) lower bounds, for other connectivity problems, especially those whose approximability lower bounds are derived from Minimum Label Cover.

Details

FOCS Conference 2015 Conference Paper

Pattern-Avoiding Access in Binary Search Trees

  • Parinya Chalermsook
  • Mayank Goswami 0001
  • László Kozma 0002
  • Kurt Mehlhorn
  • Thatchaphol Saranurak

The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i. e. One that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988, Munro, 2000, Demaine et al. 2009]. Despite BSTs being among the simplest data structures in computer science, and despite extensive effort over the past three decades, the conjecture remains elusive. Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the "easy" access sequences, and indeed the most fruitful research direction so far has been the study of specific sequences, whose "easiness" is captured by a parameter of interest. For instance, splay provably achieves the bound of O(nd) when d roughly measures the distances between consecutive accesses (dynamic finger), the average entropy (static optimality), or the delays between multiple accesses of an element(working set). The difficulty of proving dynamic optimality is witnessed by other highly restricted special cases that remain unresolved, one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees, no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. Pattern avoidance is a well-established concept in combinatorics, and the classes of input sequences thus defined are rich, e. g. The k = 3 case includes preorder sequences. For any sequence X with parameter k, our most general result shows that Greedy achieves the cost n*2(Α(n))O(k) where Α is the inverse Ackermann function. Furthermore, a broad subclass of parameter-k sequences has a natural combinatorial interpretation as k-decomposable sequences. For this class of inputs, we obtain an n*2O(k) bound for Greedy when preprocessing is allowed. For k = 3, these results imply (i) and (ii). To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden sub matrix theory. Further studying the intrinsic complexity of k-decomposable sequences, we make several observations. First, in order to obtain an offline optimal BST, it is enough to bound Greedy on non-decomposable access sequences. Furthermore, we show that the optimal cost for k-decomposable sequences is Theta(n log k), which is well below the proven performance of all known BST algorithms. Hence, sequences in this class can be seen as a "candidate counterexample" to dynamic optimality.

Details

FOCS Conference 2014 Conference Paper

Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs

  • Parinya Chalermsook
  • Bundit Laekhanukit
  • Danupon Nanongkai

The study of graph products is a major research topic and typically concerns the term f(G * H), e. g. , to show that f(G * H) = f(G)f(H). In this paper, we study graph products in a non-standard form f(R[G * H]) where R is a “reduction”, a transformation of any graph into an instance of an intended optimization problem. We resolve some open problems as applications. The first problem is minimum consistent deterministic finite automaton (DFA). We show a tight n 1-ϵ approximation hardness, improving the n 1/14-ϵ hardness of [Pitt and Warmuth, STOC 1989 and JACM 1993], where n is the sample size. (In fact, we also give improved hardnesses for the case of acyclic DFA and NFA.) Due to Board and Pitt [Theoretical Computer Science 1992], this implies the hardness of properly learning DFAs assuming NP ≠ RP (the weakest possible assumption). This affirmatively answers an open problem raised 25 years ago in the paper of Pitt and Warmuth and the survey of Pitt [All 1989]. Prior to our results, this hardness only follows from the stronger hardness of improperly learning DFAs, which requires stronger assumptions, i. e. , either a cryptographic or an average case complexity assumption [Kearns and Valiant STOC 1989 and J. ACM 1994; Daniely et al. STOC 2014]. The second problem is edge-disjoint paths (EDP) on directed acyclic graphs (DAGs). This problem admits an O(√n)-approximation algorithm [Chekuri, Khanna, and Shepherd, Theory of Computing 2006] and a matching Ω(√n) integrality gap, but so far only an n 1/26-ϵ hardness factor is known [Chuzhoy et al. , STOC 2007]. (n denotes the number of vertices.) Our techniques give a tight n 1/2-ϵ hardness for EDP on DAGs, thus resolving its approximability status. As by-products of our techniques: (i) We give a tight hardness of packing vertex-disjoint k-cycles for large k, complimenting [Guruswami and Lee, ECCC 2014] and matching [Krivelevich et al. , SODA 2005 and ACM Transactions on Algorithms 2007]. (ii) We give an alternative (and perhaps simpler) proof for the hardness of properly learning DNF, CNF and intersection of halfspaces [Alekhnovich et al. , FOCS 2004 and J. Comput. Syst. Sci. 2008]. Our new concept reduces the task of proving hardnesses to merely analyzing graph product inequalities, which are often as simple as textbook exercises. This concept was inspired by, and can be viewed as a generalization of, the graph product subadditivity technique we previously introduced in SODA 2013. This more general concept might be useful in proving other hardness results as well.

Details

SODA Conference 2013 Conference Paper

Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More

  • Parinya Chalermsook
  • Bundit Laekhanukit
  • Danupon Nanongkai

Graph product is a fundamental tool with rich applications in both graph theory and theoretical computer science. It is usually studied in the form f ( G * H ) where G and H are graphs, * is a graph product and f is a graph property. For example, if f is the independence number and * is the disjunctive product, then the product is known to be multiplicative: f ( G * H ) = f ( G ) f ( H ). In this paper, we study graph products in the following non-standard form: f (( G ⊕ H )* J ) where G, H and J are graphs, ⊕ and * are two different graph products and f is a graph property. We show that if f is the induced and semi-induced matching number, then for some products ⊕ and *, it is subadditive in the sense that f (( G ⊕ H ) * J ) ≤ f ( G * J ) + f ( H * J ). Moreover, when f is the poset dimension number, it is almost subadditive. As applications of this result (we only need J = K 2 here), we obtain tight hardness of approximation for various problems in discrete mathematics and computer science: bipartite induced and semi-induced matching (a. k. a. maximum expanding sequences), poset dimension, maximum feasible subsystem with 0/1 coefficients, unit-demand min-buying and single-minded pricing, donation center location, boxicity, cubicity threshold dimension and independent packing.

Details

FOCS Conference 2013 Conference Paper

Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses

  • Parinya Chalermsook
  • Bundit Laekhanukit
  • Danupon Nanongkai

We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the independent set problem, a question studied in the area of parameterized complexity. The second is the hardness of approximating the bipartite induced matching problem on bounded-degree bipartite graphs. The last in our series is the tight hardness of approximating the k-hypergraph pricing problem, a fundamental problem arising from the area of algorithmic game theory. In particular, assuming the Exponential Time Hypothesis, our two main results are: For any r larger than some constant, any r-approximation algorithm for the independent set problem must run in at least 2n 1-ε/ r 1+ε time. This nearly matches the upper bound of 2 n/r [23]. It also improves some hardness results in the domain of parameterized complexity (e. g. , [26], [19]). For any k larger than some constant, there is no polynomial time min{k 1-ε, n 1/2-ε } time min -approximation algorithm for the k-hypergraph pricing problem, where n is the number of vertices in an input graph. This almost matches the upper bound of min{O(k), Õ(√n) } min (by Balcan and Blum [3] and an algorithm in this paper). We note an interesting fact that, in contrast to n 1/2-ε hardness for polynomial-time algorithms, the k-hypergraph pricing problem admits n δ approximation for any δ > 0 in quasi-polynomial time. This puts this problem in a rare approximability class in which approximability thresholds can be improved significantly by allowing algorithms to run in quasi-polynomial time. The proofs of our hardness results rely on unexpectedly tight connections between the three problems. First, we establish a connection between the first and second problems by proving a new graph-theoretic property related to an induced matching number of dispersers. Then, we show that the n 1/2-ε hardness of the last problem follows from nearly tight subexponential time inapproximability of the first problem, illustrating a rare application of the second type of inapproximability result to the first one. Finally, to prove the subexponential-time inapproximability of the first problem, we construct a new PCP with several properties; it is sparse and has nearly-linear size, large degree, and small free-bit complexity. Our PCP requires no ground-breaking ideas but rather a very careful assembly of the existing ingredients in the PCP literature.

Details

STOC Conference 2012 Conference Paper

Approximation algorithms and hardness of integral concurrent flow

  • Parinya Chalermsook
  • Julia Chuzhoy
  • Alina Ene
  • Shi Li 0001

We study an integral counterpart of the classical Maximum Concurrent Flow problem, that we call Integral Concurrent Flow (ICF). In the basic version of this problem (basic-ICF), we are given an undirected n-vertex graph $G$ with edge capacities c(e), a subset T of vertices called terminals, and a demand D(t,t') for every pair (t,t') of the terminals. The goal is to find a maximum value λ, and a collection P of paths, such that every pair (t,t') of terminals is connected by ⌊ λ ⋅ D(t,t')⌋ paths in P, and the number of paths containing any edge e is at most c(e). We show an algorithm that achieves a poly log n-approximation for basic-ICF, while violating the edge capacities by only a constant factor. We complement this result by proving that no efficient algorithm can achieve a factor α-approximation with congestion c for any values α,c satisfying α ⋅ c=O(log log n/log log log n), unless NP ⊆ ZPTIME(n poly log n ). We then turn to study the more general group version of the problem (group=ICF), in which we are given a collection (S 1 ,T 1 ),...,(S k ,T k )} of pairs of vertex subsets, and for each 1 ≤ i ≤ k, a demand D i is specified. The goal is to find a maximum value λ and a collection P of paths, such that for each i, at least ⌊ λ ⋅ D i ⌋ paths connect the vertices of S i to the vertices of T i , while respecting the edge capacities. We show that for any 1 ≤ c ≤ O(log log n), no efficient algorithm can achieve a factor O(n 1/(2 2c+3 ) )-approximation with congestion c for the problem, unless NP ⊆ DTIME(n O(log log n) ). On the other hand, we show an efficient randomized algorithm that finds a poly log n-approximate solution with a constant congestion, if we are guaranteed that the optimal solution contains at least D ≥ k poly log n paths connecting every pair (S i ,T i ).

Details
v2026.09.13