Cut Problems in Network Design: Region Growing and Combinatorial Algorithms

Region-Growing and Combinatorial Algorithms for ?-Route Cut Problems Chaitanya Swamy University of Waterloo Joint work with and Guru Guruganesh CMU Laura Sanita University of Waterloo

Multicut problem ?2 ?1 ??-?? pairs or commodities ?2 ?3 ?3 ?1 Given: graph ?, edge costs {??},commodities (?1,?1), ,(?? ,??) Find: min-cost set of edges whose removal disconnects every ??-?? pair

Multicut problem ?2 ?1 ??-?? pairs or commodities ?2 ?3 ?3 feasible multicut solution ?1 Given: graph ?, edge costs {??},commodities (?1,?1), ,(?? ,??) Find: min-cost set of edges whose removal disconnects every ??-?? pair ?-? cut problem: special case where ? = 1 multiway cut problem: special case where there is a set ? of nodes called terminals, every pair from ? forms a commodity Multicut and multiway cut are APX-hard Multicut: no ?(1)-approx. assuming unique-games conjecture

?-route multicut (?-MC) ?2 ?1 ??-?? pairs or commodities ?2 ?3 ?3 ?1 Given: graph ?, edge costs {??},pairs (?1,?1), ,(?? ,??), ? Find: min-cost set of edges whose removal renders every ??-?? pair at most (? 1)-edge connected (So 1-MC is the standard multicut problem)

?-route multicut (?-MC) ?2 ?1 ??-?? pairs or commodities ?2 ?3 feasible solution for 2-MC (i.e., ? = 2) ?3 ?1 Given: graph ?, edge costs {??},pairs (?1,?1), ,(?? ,??), ? Find: min-cost set of edges whose removal renders every ??-?? pair at most (? 1)-edge connected (So 1-MC is the standard multicut problem) ?-route ?-? cut (?-(?,?)-cut): ?-route multiway cut (?-MWC): ?-route version of multiway cut ?-route cut problems: at least as hard as 1-route counterparts ?-route version of ?-? cut

Motivation for ?-route cuts Abstract a network attacker s problem who seeks to reduce connectivity below a threshold ( standard cut problems model complete disconnection) Connections to network interdiction problems Arise as dual objects to ?-route flows ?-route flows: fault-tolerant version of flows where we pack tuples of k edge-disjoint paths; introduced by Kishimito (K96); recent applications in network design (CEV12) ?-route cut identifies bottleneck when we seek a certain level of robustness in the network All-pairs version of ?-MC (every pair of nodes is a commodity): special case of min-cost subgraph excluding a fixed minor constant-approximation known for node-deletion version with: unit node costs (FLMS12), arbitrary node costs for ? = 3 (FJP10)

?-route cut problems turn out to be much more challenging than 1-route counterparts (will see this) Significant difficulties arise in adapting techniques (e.g., region-growing, Racke-trees) for (1-route) cut problems Look for bicriteria guarantees: (?,?)-approx. means edge-set ? of cost ?(optimum) every ??-??pair is at most ?(? 1)-edge-connected after removing ?

Our results ?-(?,?)-cut is at least as hard as densest-?-subgraph (D?S) even on uniform hypergraphs Unicriterion ?(??0.polylog(?))-approx. for ?-(?,?)-cut for some constant ?0 improve the state-of-the-art for D?S on graphs, and prove the existence of a family of one-way functions (A11) Previously only NP-hardness was known; CMRZ12 prove similar hardness for vertex-connectivity version of ?-(?,?)-cut Marked difference with 1-route cuts; justifies bicriteria approx.

Our results ?-(?,?)-cut is at least as hard as densest-?-subgraph (D?S) even on uniform hypergraphs Unicriterion ?(??0.polylog(?))-approx. for ?-(?,?)-cut unlikely Previously only NP-hardness was known For ?-route multiway cut: Devise simple combinatorial algorithms that achieve approx. ? 1 ,? 1 for unit costs, ? 1 ,? ln ? for general costs approximation in connectivity approximation in cost

Our results ?-(?,?)-cut is at least as hard as densest-?-subgraph (D?S) even on uniform hypergraphs Unicriterion ?(??0.polylog(?))-approx. for ?-(?,?)-cut unlikely Previously only NP-hardness was known For ?-route multiway cut: Devise simple combinatorial algorithms that achieve approx. ? 1 ,? 1 for unit costs, ? 1 ,? ln ? for general costs Previous best for general ?: ? 1 ,? ln1.5 ? ? ln ? ,? ln3 ? for general costs; follow from guarantees for ?-MC (CMRZ12) (polylog(?)-approx. for ? = 2,3 (CK08, KS12)) for unit costs, All-pairs problem is NP-hard for all ? 3

Our results (contd.) For ?-route multicut, develop LP-rounding algorithms Get ?(ln ?.lnln ?)-approx. for 2-MC, and (? 1 ,? ln ?.lnln ? )-approx. for ?-MC with unit costs Improves upon corresponding guarantees in CMRZ12 by ?( ln ?)-factor in cost for any fixed connectivity violation Key technical ingredient: powerful region-growing lemma capable of handling multiple metrics (obtained from LP solution) can be exploited when using recursive region-growing without incurring ?(ln2 ?)-factor inherent in previous uses (BC11, KS11, KS12) of region-growing for ?-route cuts (which is worse than cost-approximation of ?(ln1.5 ?) in CMRZ12) obtain same savings as in other uses of standard region-growing in divide-and-conquer algorithms (ENRS00) potentially has other applications

?-MWC: combinatorial algorithm ? = ? 1?: terminal-set, ? = |?|, ??? = optimal value Basic insight: Let ? be a feasible solution. Then ? ? has a multiway cut with ? (? 1) edges (Proof: Find min ?1-?2 cut in ? ?; remove its edges and repeat.) Unit costs: ? has a multiway cut with ??? + ? (? 1) edges If ??? ? ? 1 then ?????? 2.???; Else, there is a terminal ? and ?-isolating cut with 4? edges cut separating ? from all other terminals

?-MWC: combinatorial algorithm ? = ? 1?: terminal-set, ? = |?|, ??? = optimal value Unit costs: ? has a multiway cut with ??? + ? (? 1) edges If ??? ? ? 1 then ?????? 2.???; Else, there is a terminal ? and ?-isolating cut with 4? edges Algorithm for unit costs: Repeat: If a current terminal ? has a ?-isolating cut (with respect to current terminals) with 4? edges, drop ?. Return near-optimal multiway cut for remaining terminals Gives a (4,4)-approx.; can get ?,? ? -approx. for any ? > 2 ? > 2 is necessary: have examples where every terminal has an isolating cut with 2? edges, but ??????= ? .???. (Pointed out by BC11: used similar approach for single-source ?-MC and suggested that this may not work for ?-MWC.)

?-MWC: combinatorial algorithm ? = ? 1?: terminal-set, ? = |?|, ??? = optimal value Unit costs: ? has a multiway cut with ??? + ? (? 1) edges Algorithm for unit costs: drop terminals until all terminals are sufficiently highly connected; return multiway cut of remaining terminals ??? ? General costs: will now incur cost ? get ? 1 ,? ln ? -approximation to drop a terminal Algorithm for gneeral costs: Set ?? = min ??,??? ? (? 1) edges ? has a multiway cut of ? -cost 2.??? Find terminal ? that has an isolating cut ? ? of ? -cost 4.??? Can write ? = ?1 ?2 with ? ?1 4.??? Add ?1 to solution, drop ?, decrease ?, and repeat. ? ?for all ? can bound ? -cost of the extra ? ? and ?2 4?

Linear program (LP) for ?-MC Let ??= collection of ??-?? paths ??: indicates if edge ? is cut ??? : indicates if edge ? lies on min ??-?? cut in remainder graph Minimize ? ???? subject to, ? ? (??+???) 1 ???? ? = ? 1 for all ? ?,? 0. (?) for all ?, ? ?? Let ???? = optimal value of (?) Theorem: Can round an optimal solution to obtain Feasible solution of cost ? ln ?.lnln ? .???? for 2-MC Solution of cost ? ln ?.lnln ? .???? where every ??-?? pair is ?(? ) edge connected for ?-MC with unit costs

Region growing Useful tool for cut problems: View LP solution as a metric Grow a suitable ball in this metric and show that: (cost of boundary edges) can be charged to (volume of ball) Min ? ???? (?) s.t. ? ? (??+???) 1 ?,? ?? ???? ? ? ?,? 0. (Subdivide each edge into ?-edge and ??-edges) contribution of edges (partly) inside ball to LP objective Main difficulties: LP solution yields a different metric for each commodity unlike almost all applications of region growing Can only charge to ?-edges (but looking at ?-metric is useless) Need to bound cost of ?-boundary and no. of ??-boundary edges

Region growing for ?-route cut Min s.t. ? ? (??+???) 1 ?,? ??; (Subdivide each edge into ?-edge and ??-edges) ? ???? (?) ???? ? ?; ?,? 0. For any ?, can find a suitable ball in (? + ??)-metric: (cost of ?-boundary) (no. of ??-boundary edges) = ?(?) = ?. (?-volume of ball) contribution of ?-edges (partly) inside ball to LP objective Not hard to show ? = ?(ln ?) (BC11) Can at best yield ?(ln2 ?)-approximation: Ball for ? can contain ?-connected ??-?? pairs, so need to recurse in each ball and re-use ?-edges in the ball ?(ln ?) levels of recursion ? ?.ln ? = ?(ln2 ?)-approx.

Our region-growing lemma Min s.t. ? ? (??+???) 1 ?,? ??; (Subdivide each edge into ?-edge and ??-edges) ? ???? (?) ???? ? ?; ?,? 0. Given a set ? of nodes, for any ?, can find ball in (? + ??)-metric: (cost of ?-boundary) =(?-volume of ball) x (no. of ??-boundary edges) = ?(?) ?(? volume of ?) ? volume of ball ? lnln ? .ln Nicely telescopes across levels of recursion (since ?-portion is common to all commodity metrics) get overall ?(ln ?)-factor ?(ln ?.lnln ?)-approx. Similar in spirit to ENRS00, but more general: deal with different (related) metrics, can only charge to ?-volume

Our region-growing lemma Min s.t. ? ? (??+???) 1 ?,? ??; (Subdivide each edge into ?-edge and ??-edges) ? ???? (?) ???? ? ?; ?,? 0. Given a set ? of nodes, for any ?, can find ball in (? + ??)-metric: (cost of ?-boundary) =(?-volume of ball) x (no. of ??-boundary edges) = ?(?) ?(? volume of ?) ? volume of ball ? lnln ? .ln Nicely telescopes across levels of recursion (since ?-portion is common to all commodity metrics) get overall ?(ln ?)-factor ?(ln ?.lnln ?)-approx. Similar in spirit to ENRS00, but more general: deal with different (related) metrics, can only charge to ?-volume

Rounding algorithm for 2-MC Given a set ? of nodes, for any ?, can find ball in (? + ??)-metric: (cost of ?-boundary) =(?-volume of ball)x ? lnln ? .ln (no. of ??-boundary edges) 1 ?(? volume of ?) ? volume of ball (*) 1. Start with ? all nodes, ? 2. If there is a 2-edge-connected ??-?? pair in ?: Pick such an ??-?? pair. Find a region ? around ?? or ?? satisfying (*) and containing at most half the pairs in ?. 3. Add all ?-boundary edges of ? to ?. 4. Repeat on ? ?, and ?. Disjoint ?-volume Recursive call: ?(ln ?) recursion depth Get ?(ln ?.lnln ?)-approximation.

Summary and open questions For ?-MWC, we get bicriteria guarantees. Can one get uncriterion ? ?.polylog ? -approx.? (Easy to get ?-approx. for ?-(?,?)-cut.) Even for unit-costs? Cannot avoid ??-factor For ?-MC, we get ? 1 ,? ln ?.lnln ? -approx. for unit costs Similar result for general costs? Conjecture: possible via LP and region growing Current best approx. is ? ln ? ,? ln3 ? (CMVZ12)

Summary and open questions cost of boundary edges of ? excluding ? 1 most expensive edges How well can one approximate following problem: All commodities share source ?; find ? ? minimizing When ? = 1, this is sparsest cut on star demand graph: can be solved exactly For general ?, best approx. is ? ln ? ,? ln ? -approx. by reduction to partial-cover version of multicut (CMVZ12) Can one get ? 1 ,? 1 approximation, maybe using LP for corresponding ? route cut problem? (When ? = 1, this is ? (?,?) cut easy to get (2,2) approx. here.) (?,?)-approx. (?,?.ln ?)-approx. for ?-route single- source cut ??? ?:?? ?

Thank You