We introduce a new technique for designing fixed-parameter algorithms cut problems, called randomized contractions. apply our framework to obtain the first (FPT algorithms) with exponential speed up Steiner Cut and Node Multiway Cut-Uncut problems. prove that parameterized version of Unique Label Cover problem, which is base Games Conjecture, can be solved in $2^{O(k^2\log |\Sigma|)}n^4\log n$ deterministic time (even stronger, vertex-deletion variant), where $k$ number unsatisfied edges...

Given a directed graph $G$, set of $k$ terminals, and an integer $p$, the Directed Vertex Multiway Cut problem asks whether there is $S$ at most $p$ (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Edge analogous where edges. These two problems are indeed known to be equivalent. A natural generalization multiway cut Multicut problem, in which we want disconnect only given pairs instead pairs. Marx [Theoret. Comput. Sci., 351 (2006), pp. 394--406]...

Given a graph G and an integer k , the Feedback Vertex Set (FVS) problem asks if there is vertex set T of size at most that hits all cycles in graph. The first fixed-parameter algorithm for FVS undirected graphs appeared monograph Mehlhorn 1984. tractability (FPT) status directed was long-standing open until Chen et al. (STOC ’08, JACM ’08) showed it tractable by giving 4 ! · n O (1) time algorithm. There are two subset versions this problems: We given additional S vertices (resp., edges),...

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in variety of computational models including dynamic graph streams (where the input defined by sequence edge/hyperedge insertions and deletions) distributed systems such as MapReduce. case streams, use to prove following results:• Matching: Our main result for matchings there exists an O(k2) space algorithm returns edges maximum matching on assumption cardinality at most k. The best previous used...

As graphs continue to grow in size, we seek ways effectively process such data at scale. The model of streaming graph processing, which a compact summary is maintained as each edge insertion/deletion observed, an attractive one. However, few results are known for optimization problems over dynamic streams.In this paper, introduce new approach handling streams, by instead seeking solutions the parameterized versions these problems. Here, given parameter k and objective decide whether there...

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in variety of computational models including dynamic graph streams (where the input defined by sequence edge/hyperedge insertions and deletions) distributed systems such as MapReduce. case streams, use to prove following results:•Matching: Our main result for matchings there exists an Õ(k2) space algorithm returns edges maximum matching on assumption cardinality at most k. The best previous used...

We introduce a new technique for designing fixed-parameter algorithms cut problems, namely randomized contractions. With our framework: (1) obtain the first FPT algorithm parameterized version of UNIQUE LABEL COVER problem, with single exponential dependency on size cutset and alphabet. As consequence, we extend set polynomial time solvable instances GAMES to those at most O(√{log n}) violated constraints. (2) STEINER CUT problem speed-up over recent work Kawarabayashi Thorup (FOCS'11). (3)...

The behavior of users in social networks is often observed to be affected by the actions their friends. Bhawalkar et al. (ICALP '12) introduced a formal mathematical model for user engagement where each individual derives benefit proportional number its friends which are engaged. Given threshold degree k equilibrium this maximal subgraph whose minimum at least k. However dropping out individuals with degrees less than might lead cascading effect iterated withdrawals such that size becomes...

As graphs continue to grow in size, we seek ways effectively process such data at scale. The model of streaming graph processing, which a compact summary is maintained as each edge insertion/deletion observed, an attractive one. However, few results are known for optimization problems over dynamic streams.In this paper, introduce new approach handling streams, by instead seeking solutions the parameterized versions these problems. Here, given parameter k and objective decide whether there...

Given a directed graph G, set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is S at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Edge analogous where edges. These two problems indeed are known to be equivalent. A natural generalization multiway cut multicut problem, in which we want disconnect only given pairs instead pairs. Marx (Theor. Comp. Sci. 2006) showed that undirected graphs fixed-parameter...

Given a directed graph G, set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is S at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Edge analogous where edges. These two problems indeed are known to be equivalent. A natural generalization multiway cut multicut problem, in which we want disconnect only given pairs instead pairs. Marx (Theor. Comp. Sci. 2006) showed that undirected graphs fixed-parameter...

Given a vertex-weighted directed graph G = (V, E) and set T {t1, t2, ... tk} of k terminals, the objective Strongly Connected Steiner Subgraph (SCSS) problem is to find vertex H ⊆ V minimum weight such that G[H] contains ti → tj path for each i ≠ j. The NP-hard, but Feldman Ruhl (FOCS '99; SICOMP '06) gave novel nO(k) algorithm SCSS problem, where n number vertices in terminals. We explore how much easier becomes on planar graphs.• Our main algorithmic result 2O(k log k) · nO(√k) SCSS, which...

The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph G=(V,E) and set {D}subseteq V x of k demand pairs. aim is to compute the cheapest network N subseteq G for which there an s -> t path each (s,t)in {D}. It known that this notoriously hard no k^{1/4-o(1)}-approximation algorithm under Gap-ETH, even when parameterizing runtime by [Dinur & Manurangsi, ITCS 2018]. In light this, we systematically study several special cases DSN determine their parameterized...

Given a graph $G=(V,E)$ and set $T=\{ (s_i, t_i) : 1\leq i\leq k \}\subseteq V\times V$ of $k$ pairs, the $k$-vertex-disjoint-paths (resp. $k$-edge-disjoint-paths) problem asks to determine whether there exist~$k$ pairwise vertex-disjoint edge-disjoint) paths $P_1, P_2, ..., P_k$ in $G$ such that, for each $1\leq k$, $P_i$ connects $s_i$ $t_i$. Both edge-disjoint versions undirected graphs are famously known be FPT (parameterized by $k$) due Graph Minor Theory Robertson Seymour....