Abstract. Given a graph [Formula: see text] and a set [Formula: see text] of [Formula: see text] pairs, the Vertex-Disjoint Paths (resp., Edge-Disjoint Paths) problems asks us to determine whether there exist pairwise vertex-disjoint (resp., edge-disjoint) paths [Formula: see text] in [Formula: see text] such that [Formula: see text] connects [Formula: see text] to [Formula: see text] for each [Formula: see text]. Unlike their undirected counterparts which are FPT (parameterized by [Formula: see text]) from graph minor theory, both the edge-disjoint and vertex-disjoint versions in directed graphs were shown by Fortune, Hopcroft, and Wyllie (TCS ’80) to be NP-hard for [Formula: see text]. This strong hardness for Disjoint Paths on general directed graphs led to the study of parameterized complexity on special graph classes, e.g., when the underlying undirected graph is planar. For Vertex-Disjoint Paths on planar directed graphs, Schrijver (SICOMP ’94) designed an [Formula: see text] time algorithm which was later improved upon by Cygan et al. (FOCS ’13), who designed an FPT algorithm running in [Formula: see text] time. To the best of our knowledge, the parameterized complexity of Edge-Disjoint Paths on planar) directed graphs is unknown. We resolve this gap by showing that Edge-Disjoint Paths is W[1]-hard parameterized by the number [Formula: see text] of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA ’03, SIDMA ’10). Moreover, under the exponential time hypothesis (ETH), we show that there is no [Formula: see text] algorithm for Edge-Disjoint Paths on planar DAGs, where [Formula: see text] is the number of terminal pairs, [Formula: see text] is the number of vertices, and [Formula: see text] is any computable function. Our hardness holds even if both the maximum in-degree and the maximum out-degrees of the graph are at most 2. We now place our result in the context of previously known algorithms and hardness for Edge-Disjoint Paths on special classes of directed graphs. Implications for Edge-Disjoint Paths on DAGs: Our result shows that the [Formula: see text] algorithm of Fortune, Hopcroft, and Wyllie (TCS ’80) for Edge-Disjoint Paths on DAGs is asymptotically tight, even if we add an extra restriction of planarity. The previous best lower bound (also under ETH) for Edge-Disjoint Paths on DAGs was [Formula: see text] by Amiri et al. (MFCS ’16, IPL ’19), which improved upon the [Formula: see text] lower bound implicit in Slivkins (ESA ’03, SIDMA ’10). Implications for Edge-Disjoint Paths on planar directed graphs: As a special case of our result, we obtain that Edge-Disjoint Paths on planar directed graphs is W[1]-hard parameterized by the number [Formula: see text] of terminal pairs. This answers a question of Cygan et al. (FOCS ’13) and Schrijver (pp. 417–444, Building Bridges II, ’19) and completes the landscape of the parameterized complexity status of edge and vertex versions of the Disjoint Paths problem on planar directed and planar undirected graphs.

One of the most commonly used classification techniques is the nearest neighbor rule: given a training set $T$ of labeled points in a metric space $(\mathcal{X},\rho)$, a new unlabeled point $x\in \mathcal{X}$ is assigned the label of its nearest neighbor in $T$. To improve both the space & time complexity of this classification, it is desirable to reduce the size of the training set without compromising too much on the accuracy of the classification. Hart (1968) formalized this as the \textsc{Nearest Neighbor Condensation} (NNC) problem: find a subset $C\subseteq T$ of minimum size which is \emph{consistent} with $T$, i.e., each point $t\in T$ has the same label as that of its nearest neighbor in $C$. This problem is known to be NP-hard (Wilfong, 1991), and the heuristics used in practice often have weak or no theoretical guarantees. We analyze this problem via the \emph{refined} lens of parameterized complexity, and obtain strong lower bounds for the $k$-\textsc{NNC}-$(\mathbb{Z}^{d},\ell_p)$ problem which asks if there is a consistent subset of size $\leq k$ for a given training set of size $n$ in the metric space $(\mathbb{Z}^d,\ell_p)$ for any $1\leq p\leq \infty$: \begin{itemize} \item The $k$-\textsc{NNC}-$(\mathbb{Z}^{d},\ell_p)$ problem is W[1]-hard parameterized by $k+d$, i.e., unless FPT = W[1], there is no $f(k,d)\cdot n^{O(1)}$ time algorithm for any computable function $f$. \item Under the Exponential Time Hypothesis (ETH), there is no $d\geq 2$ and computable function $f$ such that the $k$-\textsc{NNC}-$(\mathbb{Z}^{d},\ell_p)$ problem can be solved in $f(k,d)\cdot n^{o(k^{1-1/d})}$ time. \end{itemize} The second lower bound shows that there is a so-called (Marx and Sidiropoulos, 2014) “limited blessing of low-dimensionality”: for small $d$ some improvement \emph{might be} possible over the brute-force $n^{O(k)}$ time algorithm, but as $d$ becomes large the brute-force algorithm becomes asymptotically optimal. It also shows that the is the $n^{O(\sqrt{k})}$ time algorithm of Biniaz et al. (2019) for $k$-\textsc{NNC}-$(\mathbb{R}^{2},\ell_2)$ is asymptotically tight. Our lower bounds on the fine-grained complexity of \nnc in a sense justify the use of heuristics in practice, even though they have weak or no theoretical guarantees.

In the discrete $k$-center problem, we are given a metric space $(P,\texttt{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq P$ of $k$ centers which minimizes the maximum distance of a point in $P$ from its nearest center. For any $ε>0$, Agarwal and Procopiuc [SODA '98, Algorithmica '02] designed an $(1+ε)$-approximation algorithm for this problem in $d$-dimensional Euclidean space which runs in $O(dn\log k) + \left(\dfrac{k}ε\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$ time. In this paper we show that their algorithm is essentially optimal: if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot \left(\dfrac{1}ε\right)^{o\left(k^{1-1/d}\right)} \cdot n^{o\left(k^{1-1/d}\right)}$ time algorithm for $(1+ε)$-approximating the discrete $k$-center on $n$ points in $d$-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. We obtain our lower bound by designing a gap reduction from a $d$-dimensional constraint satisfaction problem (CSP) defined by Marx and Sidiropoulos [SoCG '14] to discrete $d$-dimensional $k$-center. As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in $n^{O\left(d\cdot k^{1-1/d}\right)}$ time for discrete $k$-center on $n$ points in $d$-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some $d\geq 2$ and some computable function $f$, there is an $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ time exact algorithm for the discrete $k$-center problem on $n$ points in $d$-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for $d=2$ and was implicit in the work of Marx [IWPEC '06]. [see paper for full abstract]

The D irected S teiner N etwork (DSN) problem takes as input a directed graph G =( V , E ) with non-negative edge-weights and a set D ⊆ V × V of k demand pairs. The aim is to compute the cheapest network N⊆ G for which there is an s\rightarrow t path for each ( s , t )∈ D. It is known that this problem is notoriously hard, as there is no k 1/4− o (1) -approximation algorithm under Gap-ETH, even when parametrizing the runtime by k [Dinur & Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k . For the bi -DSNP lanar problem, the aim is to compute a solution N⊆ G whose cost is at most that of an optimum planar solution in a bidirected graph G , i.e., for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k . We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) no PAS exists for any generalization of bi-DSNP lanar , under standard complexity assumptions. The techniques we use also imply a polynomial-sized approximate kernelization scheme (PSAKS). Additionally, we study several generalizations of bi -DSNP lanar and obtain upper and lower bounds on obtainable runtimes parameterized by k . One important special case of DSN is the S trongly C onnected S teiner S ubgraph (SCSS) problem, for which the solution network N⊆ G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists for parameter k [Chitnis et al., IPEC 2013]. We give a tight inapproximability result by showing that for k no parameterized (2 − ε)-approximation algorithm exists under Gap-ETH. Additionally, we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k .

Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2, \ldots, t_k\}$ of $k$ terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set $H\subseteq V$ of minimum weight such that $G[H]$ contains a $t_{i}\rightarrow t_j$ path for each $i\neq j$. The problem is NP-hard, but Feldman and Ruhl [ SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel $n^{O(k)}$ algorithm for the SCSS problem, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar SCSS, which is an improvement of a factor of $O(\sqrt{k})$ in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an $f(k)\cdot n^{o(\sqrt{k})}$ algorithm for any computable function $f$, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is $O(\sqrt{k})$, and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, ŭlhttps://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the $n^{O(k)}$ algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an $f(k)\cdot n^{o(k/\log k)}$ algorithm for any computable function $f$. Feldman and Ruhl generalized their $n^{O(k)}$ algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source $s_i$ there is a path to the corresponding terminal $t_i$. We show that, assuming ETH, there is no $f(k)\cdot n^{o(k)}$ time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

Parameterized complexity attempts to give a more fine-grained analysis of the complexity of problems: instead of measuring the running time as a function of only the input size, we analyze the running time with respect to additional parameters. This approach has proven to be highly successful in delineating our understanding of NP-hard problems. Given this success with the TIME resource, it seems but natural to use this approach for dealing with the SPACE resource. First attempts in this direction have considered a few individual problems, with some success: Fafianie and Kratsch [MFCS'14] and Chitnis et al. [SODA'15] introduced the notions of streaming kernels and parameterized streaming algorithms respectively. For example, the latter shows how to refine the Omega(n^2) bit lower bound for finding a minimum Vertex Cover (VC) in the streaming setting by designing an algorithm for the parameterized k-VC problem which uses O(k^{2}log n) bits. In this paper, we initiate a systematic study of graph problems from the paradigm of parameterized streaming algorithms. We first define a natural hierarchy of space complexity classes of FPS, SubPS, SemiPS, SupPS and BrutePS, and then obtain tight classifications for several well-studied graph problems such as Longest Path, Feedback Vertex Set, Dominating Set, Girth, Treewidth, etc. into this hierarchy (see Figure 1 and Table 1). On the algorithmic side, our parameterized streaming algorithms use techniques from the FPT world such as bidimensionality, iterative compression and bounded-depth search trees. On the hardness side, we obtain lower bounds for the parameterized streaming complexity of various problems via novel reductions from problems in communication complexity. We also show a general (unconditional) lower bound for space complexity of parameterized streaming algorithms for a large class of problems inspired by the recently developed frameworks for showing (conditional) kernelization lower bounds. Parameterized algorithms and streaming algorithms are approaches to cope with TIME and SPACE intractability respectively. It is our hope that this work on parameterized streaming algorithms leads to two-way flow of ideas between these two previously separated areas of theoretical computer science.

Cut problems and connectivity problems on digraphs are two well-studied classes of problems from the viewpoint of parameterized complexity. After a series of papers over the last decade, we now have (almost) tight bounds for the running time of several standard variants of these problems parameterized by two parameters: the number k of terminals and the size p of the solution. When there is evidence of FPT intractability, then the next natural alternative is to consider FPT approximations. In this paper, we show two types of results for directed cut and connectivity problems, building on existing results from the literature: first is to circumvent the hardness results for these problems by designing FPT approximation algorithms, or alternatively strengthen the existing hardness results by creating "gap-instances" under stronger hypotheses such as the (Gap-)Exponential Time Hypothesis (ETH). Formally, we show the following results: Cutting paths between a set of terminal pairs, i.e., Directed Multicut: Pilipczuk and Wahlstrom [TOCT '18] showed that Directed Multicut is W[1]-hard when parameterized by p if k=4. We complement this by showing the following two results: - Directed Multicut has a k/2-approximation in 2^{O(p^2)}* n^{O(1)} time (i.e., a 2-approximation if k=4), - Under Gap-ETH, Directed Multicut does not admit an (59/58-epsilon)-approximation in f(p)* n^{O(1)} time, for any computable function f, even if k=4. Connecting a set of terminal pairs, i.e., Directed Steiner Network (DSN): The DSN problem on general graphs is known to be W[1]-hard parameterized by p+k due to Guo et al. [SIDMA '11]. Dinur and Manurangsi [ITCS '18] further showed that there is no FPT k^{1/4-o(1)}-approximation algorithm parameterized by k, under Gap-ETH. Chitnis et al. [SODA '14] considered the restriction to special graph classes, but unfortunately this does not lead to FPT algorithms either: DSN on planar graphs is W[1]-hard parameterized by k. In this paper we consider the DSN_Planar problem which is an intermediate version: the graph is general, but we want to find a solution whose cost is at most that of an optimal planar solution (if one exists). We show the following lower bounds for DSN_Planar: - DSN_Planar has no (2-epsilon)-approximation in FPT time parameterized by k, under Gap-ETH. This answers in the negative a question of Chitnis et al. [ESA '18]. - DSN_Planar is W[1]-hard parameterized by k+p. Moreover, under ETH, there is no (1+epsilon)-approximation for DSN_Planar in f(k,p,epsilon)* n^{o(k+sqrt{p+1/epsilon})} time for any computable function f. Pairwise connecting a set of terminals, i.e., Strongly Connected Steiner Subgraph (SCSS): Guo et al. [SIDMA '11] showed that SCSS is W[1]-hard parameterized by p+k, while Chitnis et al. [SODA '14] showed that SCSS remains W[1]-hard parameterized by p, even if the input graph is planar. In this paper we consider the SCSS_Planar problem which is an intermediate version: the graph is general, but we want to find a solution whose cost is at most that of an optimal planar solution (if one exists). We show the following lower bounds for SCSS_Planar: - SCSS_Planar is W[1]-hard parameterized by k+p. Moreover, under ETH, there is no (1+epsilon)-approximation for SCSS_Planar in f(k,p,epsilon)* n^{o(sqrt{k+p+1/epsilon})} time for any computable function f. Previously, the only known FPT approximation results for SCSS applied to general graphs parameterized by k: a 2-approximation by Chitnis et al. [IPEC '13], and a matching (2-epsilon)-hardness under Gap-ETH by Chitnis et al. [ESA '18].

In the Steiner Orientation problem, the input is a mixed graph G (it has both directed and undirected edges) and a set of k terminal pairs $$\mathscr {T}$$ . The question is whether we can orient the undirected edges in a way such that there is a directed $$s\leadsto t$$ path for each terminal pair $$(s,t)\in \mathscr {T}$$ . Arkin and Hassin [DAM’02] showed that the Steiner Orientation problem is NP-complete. They also gave a polynomial time algorithm for the special case when $$k=2$$ . From the viewpoint of exact algorithms, Cygan et al. [ESA’12, SIDMA’13] designed an XP algorithm running in $$n^{O(k)}$$ time for all $$k\ge 1$$ . Pilipczuk and Wahlström [SODA’16, TOCT’18] showed that the Steiner Orientation problem is W[1]-hard parameterized by k. As a byproduct of their reduction, they were able to show that under the Exponential Time Hypothesis (ETH) of Impagliazzo, Paturi and Zane [JCSS’01] the Steiner Orientation problem does not admit an $$f(k)\cdot n^{o(k/\log k)}$$ algorithm for any computable function f. In this paper, we give a short and easy proof that the $$n^{O(k)}$$ algorithm of Cygan et al. is asymptotically optimal, even if the input graph is planar. Formally, we show that the Planar Steiner Orientation problem is W[1]-hard parameterized by the number k of terminal pairs, and, under ETH, cannot be solved in $$f(k)\cdot n^{o(k)}$$ time for any computable function f. Moreover, under a stronger hypothesis called Gap-ETH of Dinur [ECCC’16] and Manurangsi and Raghavendra [ICALP’17], we are able to show that there is no constant $$\vartheta >0$$ such that Planar Steiner Orientation admits an $$(\frac{19}{20}+\vartheta )$$ -approximation in FPT time, i.e., no $$f(k)\cdot n^{o(k)}$$ time algorithm can distinguish between the case when all k pairs are satisfiable versus the case when less than $$k \cdot (\frac{19}{20}+\vartheta )$$ pairs are satisfiable. To the best of our knowledge, this is the first FPT inapproximability result on planar graphs.

The Directed Steiner Network (DSN) problem takes as input a directed edge-weighted graph G=(V,E) and a set {D}subseteq V x V of k demand pairs. The aim is to compute the cheapest network N subseteq G for which there is an s - t path for each (s,t)in {D}. It is known that this problem is notoriously hard as there is no k^{1/4-o(1)}-approximation algorithm under Gap-ETH, even when parameterizing the runtime by k [Dinur Manurangsi, ITCS 2018]. In light of this, we systematically study several special cases of DSN and determine their parameterized approximability for the parameter k. For the bi-DSN_Planar problem, the aim is to compute a planar optimum solution N subseteq G in a bidirected graph G, i.e. for every edge uv of G the reverse edge vu exists and has the same weight. This problem is a generalization of several well-studied special cases. Our main result is that this problem admits a parameterized approximation scheme (PAS) for k. We also prove that our result is tight in the sense that (a) the runtime of our PAS cannot be significantly improved, and (b) it is unlikely that a PAS exists for any generalization of bi-DSN_Planar, unless FPT=W[1]. Additionally we study several generalizations of bi-DSN_Planar and obtain upper and lower bounds on obtainable runtimes parameterized by k. One important special case of DSN is the Strongly Connected Steiner Subgraph (SCSS) problem, for which the solution network N subseteq G needs to strongly connect a given set of k terminals. It has been observed before that for SCSS a parameterized 2-approximation exists when parameterized by k [Chitnis et al., IPEC 2013]. We show a tight inapproximability result: under Gap-ETH there is no (2-{epsilon})-approximation algorithm parameterized by k (for any epsilon0). To the best of our knowledge, this is the first example of a W[1]-hard problem admitting a non-trivial parameterized approximation factor which is also known to be tight! Additionally we show that when restricting the input of SCSS to bidirected graphs, the problem remains NP-hard but becomes FPT for k.

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results: Matching: Our main result for matchings is that there exists an Õ(k2) space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at most k. The best previous algorithm used Õ(kn) space where n is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has Õ(1) update time. We also show that there exists an Õ(n2/α3) space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first nontrivial results in the dynamic setting. Vertex Cover and Hitting Set: There exists an Õ(kd) space algorithm that solves the minimum hitting set problem where d is the cardinality of the input sets and k is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has Õ(1) update time. The case d = 2 corresponds to minimum vertex cover. Finally, we consider a larger family of parameterized problems (including b-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in $2^{O(k^2\log |\Sigma|)}n^4\log n$ deterministic time (even in the stronger, vertex-deletion variant), where $k$ is the number of unsatisfied edges and $|\Sigma|$ is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by $O(\sqrt{\log n})$ to optimality, which improves over the trivial $O(1)$ upper bound. We prove that the Steiner Cut problem can be solved in $2^{O(k^2\log k)}n^4\log n$ deterministic time and $\tilde{O}(2^{O(k^2\log k)}n^2)$ randomized time, where $k$ is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering “cut” and “uncut” constraints at the same time. More precisely, we define a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in $2^{O(k^2\log k)}n^4\log n$ deterministic time, where $k$ is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.

As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams. In this paper, we introduce a new approach to handling graph streams, by instead seeking solutions for the parameterized versions of these problems. Here, we are given a parameter k and the objective is to decide whether there is a solution bounded by k. By combining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for the parameterized versions of Maximal Matching and Vertex Cover. We consider various models for a graph stream on n nodes: the insertion-only model where the edges can only be added, and the dynamic model where edges can be both inserted and deleted. More formally, we show the following results: In the insertion only model, there is a one-pass deterministic algorithm for the parameterized Vertex Cover problem which computes a sketch using Õ(k2) space1 such that at each timestamp in time Õ(2k) it can either extract a solution of size at most k for the current instance, or report that no such solution exists. We also show a tight lower bound of Ω(k2) for the space complexity of any (randomized) streaming algorithms for the parameterized Vertex Cover, even in the insertion-only model. In the dynamic model, and under the promise that at each timestamp there is a maximal matching of size at most k, there is a one-pass Õ(k2)-space (sketch-based) dynamic algorithm that maintains a maximal matching with worst-case update time Õ(k2). This algorithm partially solves Open Problem 64 from [1]. An application of this dynamic matching algorithm is a one-pass Õ(k2)-space streaming algorithm for the parameterized Vertex Cover problem that in time Õ(2k) extracts a solution for the final instance with probability 1 – δ/no(1), where δ < 1. To the best of our knowledge, this is the first graph streaming algorithm that combines linear sketching with sequential operations that depend on the graph at the current time. In the dynamic model without any promise, there is a one-pass randomized algorithm for the parameterized Vertex Cover problem which computes a sketch using Õ(nk) space such that in time Õ(nk + 2k) it can either extract a solution of size at most k for the final instance, or report that no such solution exists.

Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].

Given a graphGand an integerk, theFeedback Vertex Set(FVS) problem asks if there is a vertex setTof size at mostkthat hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC ’08, JACM ’08) showed that it is fixed-parameter tractable by giving a 4kk! ·nO(1)time algorithm. There are two subset versions of this problems: We are given an additional subsetSof vertices (resp., edges), and we want to hit all cycles passing through a vertex ofS(resp., an edge ofS); the two variants are known to be equivalent in the parameterized sense. Recently, theSubsetFVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP’11, SIDMA’13) and independently by Kakimura et al. (SODA ’12). We generalize the result of Chen et al. (STOC ’08, JACM ’08) by showing that aSubsetFVS in directed graphs can be solved in time 2O(k3)ċnO(1)(i.e., FPT parameterized by sizekof the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC ’11, SICOMP ’14) to show thatUndirected Multicutis FPT, and it was generalized by Chitnis et al. (SODA ’12, SICOMP ’13) to directed graphs to show thatDirected Multiway Cutis FPT. In addition to proving the FPT of aDirected SubsetFVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from 22O(k)to 2O(k2)in the parameter dependence of theDirected Multiway Cutalgorithm of Chitnis et al. (SODA ’12, SICOMP ’13).

Given a vertex-weighted directed graph G = (V, E) and a set T = {t1, t2, … tk} of k terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G[H] contains a ti → tj path for each i = j. The problem is NP-hard, but Feldman and Ruhl (FOCS '99; SICOMP '06) gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a algorithm for planar SCSS, which is an improvement of a factor of in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: Our algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k) · no(k/logk) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Forest (DSF) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that that, assuming ETH, there is no f(k) · no(k) time algorithm for DSF on acyclic planar graphs.

The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. (ICALP '12) introduced a formal mathematical model for user engagement in social networks where each individual derives a benefit proportional to the number of its friends which are engaged. Given a threshold degree k the equilibrium for this model is a maximal subgraph whose minimum degree is at least k. However the dropping out of individuals with degrees less than k might lead to a cascading effect of iterated withdrawals such that the size of equilibrium subgraph becomes very small. To overcome this some special vertices called "anchors" are introduced: these vertices need not have large degree. Bhawalkar et al. considered the Anchored k-Core problem: Given a graph G and integers b, k and p do there exist sets of vertices B, H such that B is a subset of H, size of B is at most b and size of H is at least p, and every vertex v which is in H but not in B has degree at least k in the induced subgraph G[H]. They showed that the problem is NP-hard for all k greater equal 2, and gave some inapproximability and fixed-parameter intractability results. In this paper we give improved hardness results for this problem. In particular we show that the Anchored k-Core problem is W[1]-hard parameterized by p, even for k=3. This improves the result of Bhawalkar et al. (who show W[2]-hardness parameterized by b) as our parameter is always bigger since p is greater equal than b. Then we answer a question of Bhawalkar et al. by showing that the Anchored k-Core problem remains NP-hard on planar graphs for all k greater equal 3, even if the maximum degree of the graph is k+2. Finally we show that the problem is FPT on planar graphs parameterized by b for all k greater equal 7.

We consider the Directed Anchored k-Core problem, where the task is for a given directed graph G and integers b, k and p, to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k. For undirected graphs, this problem was introduced by Bhawalkar, Kleinberg, Lewi, Roughgarden, and Sharma [ICALP 2012]. We undertake a systematic analysis of the computational complexity of Directed Anchored k-Core and show that: - The decision version of the problem is NP-complete for every k>=1 even if the input graph is restricted to be a planar directed acyclic graph of maximum degree at most k+2. - The problem is fixed parameter tractable (FPT) parameterized by the size of the core p for k=1, and W[1]-hard for k>=2. - When the maximum degree of the graph is at most Delta, the problem is FPT parameterized by p+Delta if k>=Delta/2.

In this paper we propose a game-theoretic model to analyze events similar to the 2009 DARPA Network Challenge, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring the roles that the Internet and social networks play in incentivizing wide-area collaborations. The challenge was to form a group that would be the first to find the locations of ten moored weather balloons across the United States. We consider a model in which N people (who can form groups) are located in some topology with a fixed coverage volume around each person's geographical location. We consider various topologies where the players can be located such as the Euclidean d-dimension space and the vertices of a graph. A balloon is placed in the space and a group wins if it is the first one to report the location of the balloon. A larger team has a higher probability of finding the balloon, but we assume that the prize money is divided equally among the team members. Hence there is a competing tension to keep teams as small as possible.

Given a directed graph $G$, a set of $k$ terminals, and an integer $p$, the Directed Vertex Multiway Cut problem asks whether there is a set $S$ of at most $p$ (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where $S$ is a set of at most $p$ edges. These two problems are indeed known to be equivalent. A natural generalization of the multiway cut is the Multicut problem, in which we want to disconnect only a set of $k$ given pairs instead of all pairs. Marx [Theoret. Comput. Sci., 351 (2006), pp. 394--406] showed that in undirected graphs Vertex/Edge Multiway cut is fixed-parameter tractable (FPT) parameterized by $p$. Marx and Razgon [Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 469--478] showed that undirected Multicut is FPT and Directed Multicut is W[1]-hard parameterized by $p$. We complete the picture here by our main result, which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time $2^{2^{O(p)}}n^{O(1)}$, i.e., FPT parameterized by size $p$ of the cutset of the solution. This answers an open question raised by the aforementioned papers. It follows from our result that Directed Edge/Vertex Multicut is FPT for the case of $k=2$ terminal pairs, which answers another open problem raised by Marx and Razgon.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. With our framework: (1) We obtain the first FPT algorithm for the parameterized version of the UNIQUE LABEL COVER problem, with single exponential dependency on the size of the cutset and the size of the alphabet. As a consequence, we extend the set of the polynomial time solvable instances of UNIQUE GAMES to those with at most O(√{log n}) violated constraints. (2) We obtain a new FPT algorithm for the STEINER CUT problem with exponential speed-up over the recent work of Kawarabayashi and Thorup (FOCS'11). (3) We show how to combine considering 'cut' and 'uncut' constraints at the same time. We define a robust problem NODE MULTIWAY CUT-UNCUT that can serve as an abstraction of introducing uncut constraints, and show that it admits an FPT algorithm with single exponential dependency on the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle real weights, to the best of our knowledge, the technique of important separators does not work in the weighted version.

Given a directed graph G, a set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where S is a set of at most p edges. These two problems indeed are known to be equivalent. A natural generalization of the multiway cut is the multicut problem, in which we want to disconnect only a set of k given pairs instead of all pairs. Marx (Theor. Comp. Sci. 2006) showed that in undirected graphs multiway cut is fixed-parameter tractable (FPT) parameterized by p. Marx and Razgon (STOC 2011) showed that undirected multicut is FPT and directed multicut is W[1]-hard parameterized by p. We complete the picture here by our main result which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time 22O(p) nO(1), i.e., FPT parameterized by size p of the cutset of the solution. This answers an open question raised by Marx (Theor. Comp. Sci. 2006) and Marx and Razgon (STOC 2011). It follows from our result that Directed Multicut is FPT for the case of k = 2 terminal pairs, which answers another open problem raised in Marx and Razgon (STOC 2011).

Coalition formation is a key topic in multi-agent systems. Coalitions enable agents to achieve goals that they may nothave been able to achieve on their own. Previous work hasshown problems in coalition games to be computationally hard. Wooldridge and Dunne (Artifi. Intell. 2006) studied the classical computational complexity of several natural decision problems in Coalitional Resource Games (CRG) - games in which each agent is endowed with a set of resources and coalitions can bring about a set of goals if they are collectively endowed with the necessary amount of resources. The input of coalitional resource games bundles together several elements, e.g., the agent set Ag, the goal set G, the resource set R, etc. Shrot et al. (AAMAS 2009) examine coalition formation problems in the CRG model using the theory of Parameterized Complexity. Their refined analysis shows that not all parts of input act equal - some instances of the problem are indeed tractable while others still remain intractable.We answer an important question left open by Shrot, Aumann,and Kraus by showing that the SC Problem (checking whether a Coalition is Successful) is W[1]-hard when parameterized by the size of the coalition. Then via a single theme of reduction from SC, we are able to show that various problems related to resources, resource bounds, and resource conflicts introduced by Wooldridge et al. are (i) W[1]-hard or co-W[1]-hard w.r.t the size of the coalition; and (ii) Para-NP hard or co-Para-NP-hard w.r.t |R|. When parameterized by |G| or |R| + |Ag|, we give a general algorithm which proves that these problems are indeed tractable.