Author name cluster

Bundit Laekhanukit

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.

16 papers

1 author row

SODA Conference 2022 Conference Paper

Polynomial Integrality Gap of Flow LP for Directed Steiner Tree

Shi Li 0001
Bundit Laekhanukit

In the Directed Steiner Tree (DST) problem, we are given a directed graph G = (V, E ) on n vertices with edge-costs, a root vertex r, and a set K of k terminals. The goal is to find a minimum-cost subgraph of G that contains a path from r to every terminal t ∊ k. DST has been a notorious problem for decades as there is a large gap between the best-known polynomial-time approximation ratio of O ( k∊ ) for any constant ∊ > 0, and the best quasi-polynomial-time approximation ratio of. Towards understanding this gap, we study the integrality gap of the standard flow LP relaxation for the problem. We show that the LP has an integrality gap polynomial in n. Previously, the integrality gap LP is only known to be [Halperin et al. , SODA'03 & SIAM J. Comput. ] and [Zosin-Khuller, SODA'02] in some instance with. Our result gives the first known lower bound on the integrality gap of this standard LP that is polynomial in n, the number of vertices. Consequently, we rule out the possibility of developing a poly-logarithmic approximation algorithm for the problem based on the flow LP relaxation.

FOCS Conference 2022 Conference Paper

Survivable Network Design Revisited: Group-Connectivity

Qingyun Chen
Bundit Laekhanukit
Chao Liao
Yuhao Zhang 0001

In the classical survivable network design problem (SNDP), we are given an undirected graph $G-(V, E)$ with costs on edges and a connectivity requirement $k(5, t)$ for each pair of vertices. The goal is to find a minimum-cost subgraph $H\sqsubseteq G$ such that every pair $(s, t)$ are connected by $k(s, t)$ edge or (openly) vertex disjoint paths, abbreviated as EC-SNDP and VC-SNDP, respectively. The seminal result of Jain [FOCS’98, Combinatorica’01] gives a 2-approximation algorithm for EC-SNDP, and a decade later, an $O(k^{3}\log n)-$ approximation algorithm for VC-SNDP, where k is the largest connectivity requirement, was discovered by Chuzhoy and Khanna [FOCS’09, Theory Comput’12]. While there is a rich literature on point-to-point settings of SNDP, the viable case of connectivity between subsets is still relatively poorly understood. This paper concerns the generalization of SNDP into the subset-to-subset setting, namely Group EC-SNDR We develop the framework, which yields the first non-trivial (true) approximation algorithm for Group. EC-SNDE Previously only a bicriteria approximation algorithm is known for Group EC-SNDP [Chalermsook, Grandoni, and Laekhanukit, SODA’15l, and a true approximation algorithm is known only for the single-source variant with connectivity requirement $k(S, T)\in\{0, 1, 2\}$ [Gupta, Krishnaswamy, and Ravi, SODA’10; Khandekar, Kortsarz, and Nutov, FSTTCS’09 and Theor Comput. Sci’12].

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.

STOC Conference 2019 Conference Paper

O (log 2 k / log log k )-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm

Fabrizio Grandoni 0001
Bundit Laekhanukit
Shi Li 0001

In the Directed Steiner Tree (DST) problem we are given an n-vertex directed edge-weighted graph, a root r , and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log^2 k /log log k )-approximation algorithm for DST that runs in quasi-polynomial-time, i.e., in time n^polylog(k). By making standard complexity assumptions, we show the matching lower bound of Omega(log^2 k/loglogk) for the class of quasi-polynomial time algorithms, meaning that our approximation ratio is asymptotically the best possible. This is the first improvement on the DST problem since the classical quasi-polynomial-time O (log^3 k ) approximation algorithm by Charikar et al. [SODA’98J. Algorithms’99]. (The paper erroneously claims an O (log^2 k ) approximation due to a mistake in prior work.)

STOC Conference 2018 Conference Paper

On the parameterized complexity of approximating dominating set

Karthik C. S. 0001
Bundit Laekhanukit
Pasin Manurangsi

We study the parameterized complexity of approximating the k -Dominating Set (domset) problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a dominating set of size at most F ( k ) · k whenever the graph G has a dominating set of size k . When such an algorithm runs in time T ( k )poly( n ) (i.e., FPT-time) for some computable function T , it is said to be an F ( k )-FPT-approximation algorithm for k -domset. Whether such an algorithm exists is listed in the seminal book of Downey and Fellows (2013) as one of the ”most infamous” open problems in Parameterized Complexity. This work gives an almost complete answer to this question by showing the non-existence of such an algorithm under W[1]≠FPT and further providing tighter running time lower bounds under stronger hypotheses. Specifically, we prove the following for every computable functions T , F and every constant ε > 0: (i) Assuming W[1]≠FPT, there is no F ( k )-FPT-approximation algorithm for k -domset, (ii) Assuming the Exponential Time Hypothesis (ETH), there is no F ( k )-approximation algorithm for k -domset that runs in T ( k ) n o ( k ) time, (iii) Assuming the Strong Exponential Time Hypothesis (SETH), for every integer k ≥ 2, there is no F ( k )-approximation algorithm for k -domset that runs in T ( k ) n k − ε time, (iv) Assuming the k -sum Hypothesis, for every integer k ≥ 3, there is no F ( k )-approximation algorithm for k -domset that runs in T ( k ) n ⌈ k /2 ⌉ − ε time. Previously, only constant ratio FPT-approximation algorithms were ruled out under W[1]≠FPT and (log 1/4 − ε k )-FPT-approximation algorithms were ruled out under ETH [Chen and Lin, FOCS 2016]. Recently, the non-existence of an F ( k )-FPT-approximation algorithm for any function F was shown under gapETH [Chalermsook et al., FOCS 2017]. Note that, to the best of our knowledge, no running time lower bound of the form n δ k for any absolute constant δ > 0 was known before even for any constant factor inapproximation ratio. Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of Abboud et al. [FOCS 2017]. Specifically, we show that to prove hardness of approximation of a certain parameterized variant of the label cover problem, it suffices to devise a specific protocol for a communication problem that depends on which hypothesis we rely on. Each of these communication problems turns out to be either a well studied problem or a variant of one; this allows us to easily apply known techniques to solve them.

SODA Conference 2017 Conference Paper

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

Eden Chlamtac
Michael Dinitz
Guy Kortsarz
Bundit Laekhanukit

It was recently found that there are very close connectionsbetween the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA ‘16, Bodwin-Williams SODA ‘16]. We study these problemsfrom an optimization point of view, where ratherthan studying the existence of extremal instances we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O ( n 3/5+∊ )-approximation for distance preservers and pairwisespanners (for arbitrary constant ∊ > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O (log n )-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O (1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O ( n 3/5+∊ )- approximation for the Directed Steiner Forest problem (for arbitrary constant ∊ > 0) when all edges have uniform costs, improving the previous best O ( n 2/3+∊ )- approximation due to Berman et al. [ICALP ‘11] (whichholds for general edge costs).

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.

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.

STOC Conference 2017 Conference Paper

Surviving in directed graphs: a quasi-polynomial-time polylogarithmic approximation for two-connected directed Steiner tree

Fabrizio Grandoni 0001
Bundit Laekhanukit

Real-word networks are often prone to failures. A reliable network needs to cope with this situation and must provide a backup communication channel. This motivates the study of survivable network design , which has been a focus of research for a few decades. To date, survivable network design problems on undirected graphs are well-understood. For example, there is a 2 approximation in the case of edge failures [Jain, FOCS'98/Combinatorica'01]. The problems on directed graphs , in contrast, have seen very little progress. Most techniques for the undirected case like primal-dual and iterative rounding methods do not seem to extend to the directed case. Almost no non-trivial approximation algorithm is known even for a simple case where we wish to design a network that tolerates a single failure.

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.

SODA Conference 2014 Conference Paper

Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems

Bundit Laekhanukit

Optimizing parameters of Two-Prover-One-Round Game (2P1R) is an important task in PCPs literature as it would imply a smaller PCP with the same or stronger soundness. While this is a basic question in PCPs community, the connection between the parameters of PCPs and hardness of approximations is sometimes obscure to approximation algorithm community. In this paper, we investigate the connection between the parameters of 2P1R and the hardness of approximating the class of so-called connectivity problems, which includes as subclasses the survivable network design and (multi)cut problems. Based on recent development on 2P1R by Chan (STOC 2013) and several techniques in PCPs literature, we improve hardness results of some connectivity problems that are in the form k σ, for some (very) small constant σ > 0, to hardness results of the form k c for some explicit constant c, where k is a connectivity parameter. In addition, we show how to convert these hardness into hardness results of the form D c, where D is the number of demand pairs (or the number of terminals). Our results are as follows. 1. 1. For the rooted k -connectivity problem, we have hardness of This improves upon the best known hardness of k σ by Cheriyan et al. (SODA 2012). 2. 2. For the vertex-connectivity survivable network design problem, we have hardness of This improves upon the best known hardness of Ω( k σ ) by Chakraborty et al. (STOC 2008). 3. 3. For the vertex-connectivity k -route cut problem on undirected graphs, we have hardness of This improves upon the best known hardness of k σ by Chuzhoy et al. (SODA 2012).

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.

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.

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.

SODA Conference 2012 Conference Paper

Approximating rooted Steiner networks

Joseph Cheriyan
Bundit Laekhanukit
Guyslain Naves
Adrian Vetta

The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root and many sinks is as hard to approximate as the directed Steiner forest problem, and the latter is well known to be as hard to approximate as the label cover problem. Utilizing previous techniques (due to others), we strengthen these results and extend them to undirected graphs. Specifically, we give an Ω( k ∊ ) hardness bound for the rooted k -connectivity problem in undirected graphs; this addresses a recent open question of Khanna. As a consequence, we also obtain the Ω( k ∊ ) hardness of the undirected subset k -connectivity problem. Additionally, we give a result on the integrality ratio of the natural linear programming relaxation of the directed rooted k -connectivity problem.

STOC Conference 2008 Conference Paper

An o(log 2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem

Jittat Fakcharoenphol
Bundit Laekhanukit

We present an O(log n• log k)-approximation algorithm for the problem of finding k-vertex connected spanning subgraph of minimum cost, where n is the number of vertices in the input graph, and k is the connectivity requirement. Our algorithm works for both directed and undirected graphs. The best known approximation guarantees for these problems are O(ln k• min{√k,n/n-k ln k}) by Kortsarz and Nutov, and O(ln{k}) in the case of undirected graphs where n≥ 6k 2 by Cheriyan, Vempala, and Vetta. Our algorithm is the first that has a polylogarithmic guarantee for all values of k. Combining our algorithm with the algorithm of Kortsarz and Nutov in case of small k, e.g., k<n/2, we have an O(log 2 k)-approximation algorithm. As in previous work, we use the Frank-Tardos algorithm for finding k-outconnected subgraphs as a subroutine. However, with a structural lemmas that we proved, we are able to show that we need only partial solutions returned by the Frank-Tardos algorithm; thus, we can avoid paying the whole cost of the optimal solution every time the algorithm is applied.