Treffer: Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams: Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that $$\mathcal {O}(f(k) \log ^{\mathcal {O}(1)} n)$$ O ( f ( k ) log O ( 1 ) n ) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA’16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require $$\Omega (n)$$ Ω ( n ) bits of storage for any streaming algorithm; e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general $$\mathcal{F}$$ F -Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like $$\mathcal{F}$$ F -Subgraph Deletion and $$\mathcal{F}$$ F -Minor Deletion.

AN0174064926;2uh01dec.23;2023Dec11.05:01;v2.2.500

Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams 

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that O (f (k) log O (1) n) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA'16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require Ω (n) bits of storage for any streaming algorithm; e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general F -Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like F -Subgraph Deletion and F -Minor Deletion.

Keywords: FPT; Streaming algorithms; Vertex cover; Subgraph deletion problems; Minor deletion problems

An extended abstract of this paper that appeared in COCOON 2020 was titled "Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams"

Introduction

In streaming algorithms, a graph is presented as a sequence of edges. In the simplest model, we have a stream of edge arrivals, where each edge adds to the graph seen so far, or may include a dynamic mixture of arrivals and departures of edges. In either case, the primary objective is to quickly answer some basic questions over the current state of the graph, such as finding a (maximal) matching over the current graph edges, or finding a (minimum) vertex cover, while storing only a small amount of information. In the most restrictive model, we only allow <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mo>log</mo><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup><mi>n</mi><mo stretchy="false">)</mo></mrow></math> bits of space for storage. However, using standard techniques from communication complexity one can show that most problems do not admit such algorithms. Thus one relaxes this notion and defines what is called a semi-streaming model, which allows <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>n</mi><msup><mo>log</mo><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup><mi>n</mi><mo stretchy="false">)</mo></mrow></math> bits of space. This model has been extremely successful for graph streaming algorithms and a plethora of non-trivial algorithms has been designed in this model [[1], [19]]. There is a vast literature on graph streaming and we refer to the survey by McGregor [[25]] for more details. This lead to the space complexity of the algorithm and the analysis of the space complexity. We have marked blue to the change of the all bounds and the space compelxity analysis in page 10.

The theme of this paper is parameterized streaming algorithms. So, before we go into parameterized streaming let us introduce a few basic definitions in parameterized complexity. The goal of parameterized complexity is to find ways of solving NP-hard problems more efficiently than brute force: the aim is to restrict the combinatorial explosion to a parameter that is hopefully much smaller than the input size. Formally, a parameterization of a problem is assigning an integer k to each input instance. A parameterized problem is said to be fixed-parameter tractable (FPT) if there is an algorithm that solves the problem in time <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>f</mi><mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><mo>&#183;</mo><msup><mrow><mo stretchy="false">|</mo><mi>I</mi><mo stretchy="false">|</mo></mrow><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup></mrow></math> , where <math xmlns="http://www.w3.org/1998/Math/MathML"><mfenced close="|" open="|"><mi>I</mi></mfenced></math> is the size of the input and f is an arbitrary computable function depending only on the parameter k. There is a long list of NP-hard graph problems that are FPT under various parameterizations: finding a vertex cover of size k, finding a cycle of length k, finding a maximum independent set in a graph of treewidth at most k, etc. For more details, the reader is referred to the monograph [[10]]. Given the definition of FPT for parameterized problems, it is natural to seek an efficient algorithm for the corresponding parameterized streaming versions to allow <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>f</mi><mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><msup><mo>log</mo><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup><mi>n</mi><mo stretchy="false">)</mo></mrow></math> bits of space, where f is an arbitrary computable function depending on the parameter k.

There are several ways to formalize the parameterized streaming question, and in literature certain natural models are considered. The basic case is when the input of a given problem consists of a sequence of edge arrivals only, for which one seeks a parameterized streaming algorithm (PSA). It is more challenging when the input stream is dynamic, and contains both deletions and insertions of edges. In this case one seeks a dynamic parameterized streaming algorithm (DPSA). To understand the challenges to designing DPSA, consider the problem of maintaining maximal matching over a dynamic stream. Suppose an edge or multiple edges gets deleted from a maximal matching (which may be unique) then one may need to do a substantial amount of work and also store enough information to move to a new maximal matching in a modified graph. If we are promised that at every timestamp there is a solution of cost k, then we seek a promised dynamic parameterized streaming algorithm (PDPSA). These notions were formalized in the following two papers [[6]] and several results for Vertex Cover and Maximum Matching were presented there. Unfortunately, this relaxation to <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>f</mi><mrow><mo stretchy="false">(</mo><mi>k</mi><mo stretchy="false">)</mo></mrow><msup><mo>log</mo><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></msup><mi>n</mi><mo stretchy="false">)</mo></mrow></math> bits of space does not buy us too many new results. Most of the problems for which parameterized streaming algorithms are known are "local problems". Also, problems that require some global checking – such as Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal etc. remain elusive. In fact, one can show that, when edges of the graph arrive in an arbitrary order, using reductions from communication complexity, all of the above problems will require <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> space even if we allow a constant number of passes over the data stream [[7]].

The starting point of this paper is the above mentioned <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> lower bounds on basic graph problems. We ask the most natural question – how do we deconstruct these intractability results? When we look deeper we realize that, to the best of our knowledge the only parameter that has been used in parameterized streaming algorithms is the size of the solution that we are seeking in most of the works. Indeed this is the most well-studied parameter, but there is no reason to only use solution size as a parameter. In effect, researchers have looked at structural parameters in parameterized streaming; we review them later. In parameterized complexity, when faced with obstacles, we either study a problem with respect to parameters larger than the solution size or consider some structural parameters.

Parameters, Models, And Problems

<bold>What parameters to use?</bold> In parameterized complexity, after solution size and treewidth, arguably the most notable structural parameter is vertex cover size K [[10], [15]]. For all the vertex deletion problems that we consider in this paper, a vertex cover is also a solution. Thus, the vertex cover size K is always larger than the solution size k for all the above problems. We do a thorough study of vertex deletion problems from the view point of parameterized streaming in all known models. The contribution of this paper is to carry forward the use of structural parameters in parameterized streaming algorithms as done earlier in [[7], [14]].

<bold>Streaming models.</bold> The models that we consider are: (1) Edge Arrival (Ea) model; (2) Dynamic Edge Arrival (Dea) model; (3) Vertex Arrival (Va) model (In each step, a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>v</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> is revealed along with all the edges between v and already revealed neighbors of v.); and (4) Adjacency List (Al) model (In a step, a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>v</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> is revealed along with all edges incident on v). The formal definitions are in Section 2.

<bold>What problems to study?</bold> We study the streaming complexity of parameterized versions of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion. These problems are one of the most well studied ones in parameterized complexity [[5], [12], [15], [17], [21], [23], [29], [31]] and have led to development of the field. The parameters we consider in this paper are (i) the solution size k and (ii) the size K of the vertex cover of the input graph G. In <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion, the objective is to decide whether there exists <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8834;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> of size at most k such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> has no graphs in <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> as a subgraph and has no graphs in <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> as a minor, respectively. <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion are interesting due to the following reasons. Feedback Vertex set (FVS), Even Cycle Transversal (ECT), Odd Cycle Transversal (OCT) and Triangle Deletion (TD) are special cases of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">F</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mi>C</mi><mn>3</mn></msub><mo>,</mo><msub><mi>C</mi><mn>4</mn></msub><mo>,</mo><msub><mi>C</mi><mn>5</mn></msub><mo>,</mo><mo>...</mo><mo stretchy="false">}</mo></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">F</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mi>C</mi><mn>3</mn></msub><mo>,</mo><msub><mi>C</mi><mn>5</mn></msub><mo>,</mo><mo>...</mo><mo stretchy="false">}</mo></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">F</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mi>C</mi><mn>4</mn></msub><mo>,</mo><msub><mi>C</mi><mn>6</mn></msub><mo>,</mo><mo>...</mo><mo stretchy="false">}</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">F</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mi>C</mi><mn>3</mn></msub><mo stretchy="false">}</mo></mrow></math> , respectively. FVS is also a special case of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">F</mi><mo>=</mo><mo stretchy="false">{</mo><msub><mi>C</mi><mn>3</mn></msub><mo stretchy="false">}</mo></mrow></math> .

Our Results

Let a graph G and a non-negative integer k be the inputs to the graph problems we consider. Notice that for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>K</mi><mo>&#8805;</mo><mi>k</mi></mrow></math> . In particular, we obtain a range of streaming algorithms as well as lower bounds on streaming complexity for the problems we consider. Informally, for a streaming model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> and a parameterized problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , if there is a p-pass randomized streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> that uses <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>&#8467;</mi><mo stretchy="false">)</mo></mrow></math> space then we say that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>&#8467;</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamable. Similarly, if there is no p-pass algorithm using <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>o</mi><mo stretchy="false">(</mo><mi>&#8467;</mi><mo stretchy="false">)</mo></mrow></math> bits[1] of storage then <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is said to be <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>&#8467;</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard. For formal definitions please refer to Section 2. When we omit p, it means we are considering one pass of the input stream. The highlight of our results are captured by the <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion problems.

Theorem 1.1

Consider <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion in the Al model. Parameterized by solution size k, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard. However, when parameterized by vertex cover K, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#916;</mi><msup><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mn>2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> -streamable. Here <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow></math> is the maximum degree of any graph in <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> .

The above Theorem is in contrast to results shown in [[7]]. First, we would like to point out that to the best of our knowledge this is the first set of results on hardness in the Al model. The results in [[7]] showed that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow></math> -hard. A hardness result in the Al model implies one in the Ea model (Refer to Section 2). Thus, our result (Proof in Theorem 5.1) implies a stronger lower bound for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion particularly in the Ea model. On the positive side, we show that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion parameterized by the vertex cover size K, is <math xmlns="http://www.w3.org/1998/Math/MathML"><mfenced close=")" open="("><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mo>&#183;</mo><msup><mi>K</mi><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow></msup></mfenced></math> -streamable (Proof in Theorem 4.1).

Our hardness results are obtained from reductions from well-known problems in communication complexity. The problems we reduced from are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Index</mtext><mi>n</mi></msub></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> (Please refer to Section 5.1 for details). In order to obtain the algorithm, one of the main technical contributions of this paper is the introduction of the Common Neighbor problem which plays a crucial role in designing streaming algorithms in this paper. We show that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and many of the other considered problems, like <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion parameterized by vertex cover size K, have a unifying structure that can be solved via Common Neighbor, when the edges of the graph are arriving in the Al model. In Common Neighbor problem, we are given two parameters d and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> called as degree parameter and common neighbor parameter respectively. The objective is to obtain from the input graph G, a subgraph H such that H contains the set of vertices V(M) in the maximal matching M (obtained from the streaming), all edges between the vertices in V(M), and some other vertices and edges such that any <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></math> with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>S</mi></mfenced><mo>&#8804;</mo><mi>d</mi></mrow></math> we have enough common neighbors of S. Using structural properties of such a subgraph, called the common neighbor subgraph, we show that it is enough to solve <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion on the common neighbor subgraph. Similar algorithmic and lower bound results can be obtained for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion. The following theorem can be proven using Theorem 4.4 in Section 3 and Theorem 5.1 in Section 6.

Theorem 1.2

Consider <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion in the Al model. Parameterized by solution size k, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard. However, when parameterized by vertex cover K, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#916;</mi><msup><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mn>2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> -streamable. Here <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow></math> is the maximum degree of any graph in <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> .

Though we have mentioned the main algorithmic and lower bound results in the above theorems, we have a list of other algorithmic and lower bound results in the different streaming models. The full list of results are summed up in Table 1. To understand the full strength of our contribution, we request the reader to go to Section 2 to see the relations between different streaming models and the notion of hardness and streamability.

Table 1 A summary of our results. "str." means streamable

<table frame="hsides" rules="groups"><thead><tr><th align="left"><p>Problem</p></th><th align="left"><p>Parameter</p></th><th align="left"><p><sc>Al</sc> model</p></th><th align="left"><p><sc>Va</sc> model</p></th><th align="left"><p><sc>Ea</sc>/<sc>Dea</sc> model</p></th></tr></thead><tbody><tr><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script" xmlns="">F</mi></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq76.gif" />-<sc>Subgraph Deletion</sc></p></td><td align="left"><p><italic>k</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq77.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq78.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq79.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq80.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq81.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq82.gif" />-hard<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mo>&#8224;</mo></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq83.gif" /></p></td></tr><tr><td align="left" /><td align="left"><p><italic>K</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#916;</mi><msup><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mn>2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq84.gif" />-str.<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mrow><mrow /><mo>&#8727;</mo></mrow></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq85.gif" /></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq86.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq87.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p>(Theorem 4.1)</p></td><td align="left" /><td align="left" /></tr><tr><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script" xmlns="">F</mi></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq88.gif" />-<sc>Minor</sc><sc>Deletion</sc></p></td><td align="left"><p><italic>k</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq89.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq90.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq91.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq92.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq93.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq94.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left"><p><italic>K</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#916;</mi><msup><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mn>2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq95.gif" />-str.<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mrow><mrow /><mo>&#8727;</mo></mrow></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq96.gif" /></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq97.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq98.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p>(Theorem 4.4)</p></td><td align="left" /><td align="left" /></tr><tr><td align="left"><p>FVS, <sc>ECT</sc>, <sc>OCT</sc></p></td><td align="left"><p><italic>k</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq99.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq100.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq101.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq102.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq103.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq104.gif" />-hard<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mo>&#8224;</mo></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq105.gif" /></p></td></tr><tr><td align="left" /><td align="left"><p><italic>K</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi>K</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq106.gif" />-str.<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mrow><mrow /><mo>&#8727;</mo></mrow></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq107.gif" /></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq108.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq109.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p>(Corollary 4.2)</p></td><td align="left" /><td align="left" /></tr><tr><td align="left"><p><sc>TD</sc></p></td><td align="left"><p><italic>k</italic></p></td><td align="left"><p>OPEN</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq110.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq111.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left" /><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq112.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq113.gif" />-hard<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mo>&#8224;</mo></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq114.gif" /></p></td></tr><tr><td align="left" /><td align="left"><p><italic>K</italic></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi>K</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq115.gif" />-str.<math xmlns="http://www.w3.org/1998/Math/MathML"><msup xmlns=""><mrow /><mrow><mrow /><mo>&#8727;</mo></mrow></msup></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq116.gif" /></p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq117.gif" />-hard</p></td><td align="left"><p><math xmlns="http://www.w3.org/1998/Math/MathML"><mrow xmlns=""><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math><inline-graphic href="224&#95;2023&#95;10136&#95;Article&#95;IEq118.gif" />-hard</p></td></tr><tr><td align="left" /><td align="left" /><td align="left"><p>(Corollary 4.2)</p></td><td align="left" /><td align="left" /></tr></tbody></table>

The results marked with <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#8224;</mo></math> in Table 1 are lower bound results of Chitnis et al. [[7]]. The other lower bound results are ours, some of them being improvements over the lower bound results of Chitnis et al. [[7]]. The full set of lower bound results for FVS, ECT, OCT are proven in Theorem 5.1. The lower bound results for TD is proved in Theorem 5.2. Notice that the lower bound results depend only on n. The hardness results are even stronger than what is mentioned in the above table. The nuances are mentioned in respective Theorems 5.1 and Theorem 5.2 in Section 5. Algorithmic results marked <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow /><mo>&#8727;</mo></mrow></math> are deterministic

Related Work

Problems in class P have been extensively studied in streaming complexity [[25]] in the last decade. Recently, there has been a lot of interest in studying streaming complexity of NP-hard problems like Hitting Set, Set Cover, Max Cut and Max CSP [[1], [19]]. Structural parameters have been considered to study Matching in streaming [[3], [7], [11], [14], [26]]. Fafianie and Kratsch [[16]] were the first to study parameterized streaming complexity of NP-hard problems like d-Hitting Set and Edge Dominating Set in graphs. Chitnis et al. [[6]–[8]] developed a sampling technique to design efficient parameterized streaming algorithms for promised variants of Vertex Cover, d-Hitting Set problem, b-Matching etc. They also proved lower bounds for problems like <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">G</mi></math> -Free Deletion, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">G</mi></math> -Editing, Cluster Vertex Deletion etc. [[7]].

Organisation of the Paper

Section 2 contains preliminary definitions and notations. The algorithm for Common Neighbor is in Section 3, and that of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion are presented in Section 4. The lower bound proofs are given in Section 5 and we conclude the paper in Section 6. Appendix A has the formal definitions of all the problems – <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion, <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion, FVS, ECT, OCT, TD, and Common Neighbor.

Preliminaries, Models and Relationship between Models

In this section we state formally the models of streaming algorithms we use in this paper, relationship between them and some preliminary notations that we make use of.

Streaming Models

A promising prospect to deal with problems on large graphs is the study of streaming algorithms, where a compact sketch of the subgraph whose edges have been streamed/revealed so far, is stored and computations are done on this sketch. Algorithms that can access the sequence of edges of the input graph, p times in the same order, are defined as p-pass streaming algorithms. For simplicity, we refer to 1-pass streaming algorithms as streaming algorithms. The space used by a (p-pass) streaming algorithm, is defined as the streaming complexity of the algorithm. The algorithmic model to deal with streaming graphs is determined by the way the graph is revealed. Streaming algorithms for graph problems are usually studied in the following models [[9], [25], [28]]. For the upcoming discussion, V(G) and E(G) will denote the vertex and edge set, respectively of the graph G having n vertices.

Edge Arrival (Ea) model: The stream consists of edges of G in an arbitrary order.

Dynamic Edge Arrival (Dea) model: Each element of the input stream is a pair <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>e</mi><mo>,</mo><mspace width="0.333333em" /><mtext>state</mtext><mo stretchy="false">)</mo></mrow></math> , where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>e</mi><mo>&#8712;</mo><mi>E</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>state</mtext><mspace width="0.333333em" /><mo>&#8712;</mo><mo stretchy="false">{</mo><mspace width="0.333333em" /><mtext>insert,</mtext><mspace width="0.333333em" /><mspace width="0.333333em" /><mtext>delete</mtext><mspace width="0.333333em" /><mo stretchy="false">}</mo></mrow></math> describes whether e is being inserted into or deleted from the current graph.

Vertex Arrival (Va) model: The vertices of V(G) are exposed in an arbitrary order. After a vertex v is exposed, all the edges between v and neighbors of v that have already been exposed, are revealed. This set of edges are revealed one by one in an arbitrary order.

Adjacency List (Al) model: The vertices of V(G) are exposed in an arbitrary order. When a vertex v is exposed, all the edges that are incident to v, are revealed one by one in an arbitrary order. Note that in this model each edge is exposed twice, once for each exposure of an endpoint.

Streamability and Hardness

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> be a parameterized graph problem that takes as input a graph on n vertices and a parameter k. Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>f</mi><mo>:</mo><mi mathvariant="double-struck">N</mi><mo>&#215;</mo><mi mathvariant="double-struck">N</mi><mo stretchy="false">&#8594;</mo><mi mathvariant="double-struck">R</mi></mrow></math> be a computable function. For a model <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">M</mi><mo>&#8712;</mo><mo stretchy="false">{</mo><mrow><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></mrow><mo stretchy="false">}</mo></mrow></math> , whenever we say that an algorithm <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> solves <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> with space (complexity)f(n, k) in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> , we mean <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> is a randomized algorithm that for any input instance of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> gives the correct output with probability 2/3 and has streaming complexity f(n, k).

Definition 2.1

A parameterized graph problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , that takes an n-vertex graph and a parameter k as input, is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">)</mo><mi>p</mi></mrow></math> -pass hard in the Edge Arrival model, or in short <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard, if there does not exist any p-pass streaming algorithm of space complexity <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow></math> bits that can solve <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> .

Analogously, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard are defined.

Definition 2.2

A parameterized graph problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , that takes an n-vertex graph and a parameter k as input, is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">)</mo><mi>p</mi></mrow></math> -pass streamable in Edge Arrival model, or in short <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamable if there exists a p-pass streaming algorithm of space complexity <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>f</mi><mo stretchy="false">(</mo><mi>n</mi><mo>,</mo><mi>k</mi><mo stretchy="false">)</mo><mo stretchy="false">)</mo></mrow></math> words [2] that can solve <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in Edge Arrival model.

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamable, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamable and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamable are defined analogously. For simplicity, we refer to <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>f</mi><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> -hard and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>f</mi><mo>,</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> -streamable as <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>f</mi><mo stretchy="false">)</mo></mrow></math> -hard and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>f</mi><mo stretchy="false">)</mo></mrow></math> -streamable, respectively, where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">M</mi><mo>&#8712;</mo><mo stretchy="false">{</mo><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo stretchy="false">}</mo></mrow></math> .

Definition 2.3

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="script">M</mi><mn>1</mn></msub><mo>,</mo><msub><mi mathvariant="script">M</mi><mn>2</mn></msub><mo>&#8712;</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><mrow><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></mrow><mo stretchy="false">}</mo></mrow></math> be two streaming models, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>f</mi><mo>:</mo><mi mathvariant="double-struck">N</mi><mo>&#215;</mo><mi mathvariant="double-struck">N</mi><mo stretchy="false">&#8594;</mo><mi mathvariant="double-struck">R</mi></mrow></math> be a computable function, and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>p</mi><mo>&#8712;</mo><mi mathvariant="double-struck">N</mi></mrow></math> .

If for any parameterized graph problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi mathvariant="script">M</mi><mn>1</mn></msub><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hardness of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> implies <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi mathvariant="script">M</mi><mn>2</mn></msub><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hardness of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , then we say <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="script">M</mi><mn>1</mn></msub><msub><mo>&#8804;</mo><mi>h</mi></msub><msub><mi mathvariant="script">M</mi><mn>2</mn></msub></mrow></math> .

If for any parameterized graph problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi mathvariant="script">M</mi><mn>1</mn></msub><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamability of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> implies <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi mathvariant="script">M</mi><mn>2</mn></msub><mo>,</mo><mi>f</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -streamability of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> , then we say <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="script">M</mi><mn>1</mn></msub><msub><mo>&#8804;</mo><mi>s</mi></msub><msub><mi mathvariant="script">M</mi><mn>2</mn></msub></mrow></math> .

Now, from Definitions 2.1, 2.2 and 2.3, we have the following Observation.

Observation 2.4

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>h</mi></msub><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>h</mi></msub><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow></mrow></math> ; <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>h</mi></msub><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>h</mi></msub><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow></mrow></math> ; <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>s</mi></msub><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>s</mi></msub><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow></mrow></math> ; <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>s</mi></msub><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><msub><mo>&#8804;</mo><mi>s</mi></msub><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></mrow></math> .

This observation has the following implication. If we prove a lower (upper) bound result for some problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> , then it also holds in any model <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mi mathvariant="script">M</mi></mrow><mo>&#8242;</mo></msup></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">M</mi><msub><mo>&#8804;</mo><mi>h</mi></msub><msup><mrow><mi mathvariant="script">M</mi></mrow><mo>&#8242;</mo></msup></mrow></math> ( <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">M</mi><msub><mo>&#8804;</mo><mi>s</mi></msub><msup><mrow><mi mathvariant="script">M</mi></mrow><mo>&#8242;</mo></msup></mrow></math> ). For example, if we prove a lower bound result in Al or Va model, it also holds in Ea and Dea model; if we prove an upper bound result in Dea model, it also holds in Ea, Va and Al model. In general, there is no direct connection between Al and Va. In Al and Va, the vertices are exposed in an arbitrary order. However, we can say the following when the vertices arrive in a fixed (known) order.

Observation 2.5

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></mrow><mo>&#8242;</mo></msup></math> ( <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow></mrow><mo>&#8242;</mo></msup></math> ) be the restricted version of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></math> ( <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow></math> ), where the vertices are exposed in a fixed (known) order. Then <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></mrow><mo>&#8242;</mo></msup><msub><mo>&#8804;</mo><mi>h</mi></msub><msup><mrow><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow></mrow><mo>&#8242;</mo></msup></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msup><mrow><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow></mrow><mo>&#8242;</mo></msup><msub><mo>&#8804;</mo><mi>s</mi></msub><msup><mrow><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow></mrow><mo>&#8242;</mo></msup></mrow></math> .

Next is a remark on the implication of the relation between different models discussed in this section to our results mentioned in Table 1.

Remark 1

In Table 1, the lower bound results in Va and Al hold even if we know the sequence in which vertices are exposed, and the upper bound results hold even if the vertices arrive in an arbitrary order. In general, the lower bound in the Al model for some problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> does not imply the lower bound in the Va model for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> . However, our lower bound proofs in the Al model hold even if we know the order in which vertices are exposed. So, the lower bounds for FVS, ECT, OCT in the Al model imply the lower bound in the Va model. By Observations 2.4 and 2.5, we will be done by showing a subset of the algorithmic and lower bound results mentioned in the Table 1.

General Notation

The set <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><mn>1</mn><mo>,</mo><mo>...</mo><mo>,</mo><mi>n</mi><mo stretchy="false">}</mo></mrow></math> is denoted as [n]. Without loss of generality, we assume that the number of vertices in the graph is n, which is a power of 2. Given an integer <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>r</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><msub><mo>log</mo><mn>2</mn></msub><mi>n</mi><mo stretchy="false">]</mo></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>bit</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>r</mi><mo stretchy="false">)</mo></mrow></math> denotes the <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>r</mi><mtext>-th</mtext><mspace width="0.333333em" /></mrow></math> bit in the bit expansion of i. The union of two graphs <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>G</mi><mn>1</mn></msub></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>G</mi><mn>2</mn></msub></math> with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>1</mn></msub><mo stretchy="false">)</mo></mrow><mo>=</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>2</mn></msub><mo stretchy="false">)</mo></mrow></mrow></math> , is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>G</mi><mn>1</mn></msub><mo>&#8746;</mo><msub><mi>G</mi><mn>2</mn></msub></mrow></math> , where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>1</mn></msub><mo>&#8746;</mo><msub><mi>G</mi><mn>2</mn></msub><mo stretchy="false">)</mo></mrow><mo>=</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>1</mn></msub><mo stretchy="false">)</mo></mrow><mo>=</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>2</mn></msub><mo stretchy="false">)</mo></mrow></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>1</mn></msub><mo>&#8746;</mo><msub><mi>G</mi><mn>2</mn></msub><mo stretchy="false">)</mo></mrow><mo>=</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>1</mn></msub><mo stretchy="false">)</mo></mrow><mo>&#8746;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>G</mi><mn>2</mn></msub><mo stretchy="false">)</mo></mrow></mrow></math> . For <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> is the subgraph of G induced by <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> . The degree of a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> , is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>deg</mtext><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>u</mi><mo stretchy="false">)</mo></mrow></mrow></math> . The maximum and average degrees of the vertices in G are denoted as <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> , respectively. For a family of graphs <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><munder><mo movablelimits="false">max</mo><mrow><mi>F</mi><mo>&#8712;</mo><mi mathvariant="script">F</mi></mrow></munder><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mrow></mrow></math> . A graph F is a subgraph of a graph G if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>E</mi><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo><mo>&#8838;</mo><mi>E</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> be the set of edges that can be formed only between vertices of V(F). A graph F is said to be a minor of a graph G if F can be obtained from G by deleting edges and vertices and by contracting edges. The neighborhood of a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>v</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> . For <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mi mathvariant="bold">N</mi><mi mathvariant="bold">G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">S</mi><mo stretchy="false">)</mo></mrow></mrow></math> denotes the set of vertices in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>S</mi></mrow></math> that are neighbors of every vertex in S. A vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>v</mi><mo>&#8712;</mo><mrow><msubsup><mi mathvariant="bold">N</mi><mi mathvariant="bold">G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">S</mi><mo stretchy="false">)</mo></mrow></mrow></mrow></math> is said to be a common neighbor of S in G. The size of any minimum vertex cover in G is denoted by <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> . A cycle on the sequence of vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></math> is denoted as <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo stretchy="false">)</mo></mrow></math> . For a matching M in G, the vertices in the matching are denoted by V(M). <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>C</mi><mi>t</mi></msub></math> denotes a cycle of length t. <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>P</mi><mi>t</mi></msub></math> denotes a path having t vertices.

Common Neighbor Problem (useful subroutine in our algorithms)

In the next Section, we show that <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi mathvariant="normal">&#916;</mi><msup><mrow><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow><mn>2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> -streamable when the vertex cover of the input graph is parameterized by K. This will imply that FVS, ECT, OCT and TD parameterized by vertex cover size K, are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi>K</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></math> -streamable. This complements the results in Theorems 5.1 and 5.2 that show that the problems parameterized by vertex cover size K are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard. Note that by Observation 2.4, this also implies that the problems parameterized by vertex cover size K are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">M</mi><mo>&#8712;</mo><mo stretchy="false">{</mo><mrow><mrow><mi mathvariant="normal">E</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mrow><mi mathvariant="normal">D</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">E</mi><mi mathvariant="normal">A</mi></mstyle></mrow></mrow><mo stretchy="false">}</mo></mrow></math> . Finally, we design an algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion that is inspired by the algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion.

Common Neighbor Problem

For a graph G and parameters <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">d</mi><mo>,</mo><mi>&#8467;</mi><mo>&#8712;</mo><mi mathvariant="double-struck">N</mi></mrow></math> , H will be called a common neighbor subgraph for G if

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> such that H has no isolated vertex.

E(H) contains the edges of a maximal matching M of G along with the edges where both the endpoints are from V(M), such that for all subsets <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></math> , with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>S</mi></mfenced><mo>&#8804;</mo><mi>d</mi></mrow></math> , we have

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mi>N</mi><mi>H</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><msubsup><mi>N</mi><mi>G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mrow></math> if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><msubsup><mi>N</mi><mi>G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mfenced><mo>&#60;</mo><mi>&#8467;</mi></mrow></math> ;

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mrow><msubsup><mi>N</mi><mi>H</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo></mrow></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mfenced><mo>&#8805;</mo><mi>&#8467;</mi></mrow></math> if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><msubsup><mi>N</mi><mi>G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi>S</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mfenced><mo>&#8805;</mo><mi>&#8467;</mi></mrow></math> .

In simple words, a common neighbor subgraph H of G is an augmentation of the vertex and edge set of a maximal matching M of G. For each subset S of at most d vertices in V(M), H contains edges to sufficiently many common neighbors of S in G. The parameters <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>&#8804;</mo><mi>K</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> are referred to as the degree parameter and common neighbor parameter, respectively.

Graph: Fig. 1Suppose the vertices are exposed in the increasing order of the indices. Also, when vi is exposed, edge {vi,vj} arrives first before {vi,vj′} arrives if and only if j<j′. Figure (a) shows a graph G where M={(v1,v2),(v3,v4)} is a maximal matching found by the streaming algorithm (Algorithm 3.1). Figure (b) shows the corresponding common neighbor subgraph H with degree parameter d=2 and a common neighbor parameter ℓ=2.

The Common Neighbor problem is formally defined as follows. It takes as input a graph G with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> , degree parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>&#8804;</mo><mi>K</mi></mrow></math> and common neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> and produces a common neighbor subgraph of G as the output. Common Neighbor parameterized by vertex cover size K, admits Algorithm 1.

Observe that G is a common neighbor subgraph of itself for any <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>,</mo><mi>&#8467;</mi></mrow></math> with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>1</mn><mo>&#8804;</mo><mi>d</mi><mo>,</mo><mi>&#8467;</mi><mo>&#60;</mo><mi>n</mi><mo>.</mo></mrow></math> However, when the vertex cover the input graph is at most K, our algorithm (Algorithm 1) always generates a common neighbor subgraph of size <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mi>K</mi><mn>2</mn></msup><mo>+</mo><msup><mi>K</mi><mi>d</mi></msup><mo>&#183;</mo><mi>d</mi><mi>&#8467;</mi><mo stretchy="false">)</mo></mrow></math> . Note that a graph G can have multiple common neighbor subgraphs with the given parameters d and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> . But, if the stream order is fixed, then the common neighbor subgraph generated by our algorithm is fixed. Figure 1 shows an illustration of common neighbor subgraph.

Graph: Algorithm 1Algorithm 1: Common Neighbor

Lemma 3.1

Common Neighbor, with a commmon neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> and parameterized by vertex cover size K, is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi>K</mi><mn>2</mn></msup><mo>+</mo><msup><mi>K</mi><mi>d</mi></msup><mo>&#183;</mo><mi>d</mi><mi>&#8467;</mi><mo stretchy="false">)</mo></mrow></math> -streamable.

Proof

We start our algorithm by initializing a maximal matching M with <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#8709;</mi></math> and construct M in G that is maximal under inclusion; See Algorithm 1. As <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mfenced><mo>&#8804;</mo><mi>K</mi></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>M</mi></mfenced><mo>&#8804;</mo><mi>K</mi></mrow></math> . Recall that we are considering the Al model here. Let <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>M</mi><mi>u</mi></msub></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi>M</mi><mi>u</mi><mo>&#8242;</mo></msubsup></math> be the current maximal matchings just before and after the exposure of the vertex u (including the processing of the edges adjacent to u), respectively. Note that, by construction, these partial matchings <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>M</mi><mi>u</mi></msub></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi>M</mi><mi>u</mi><mo>&#8242;</mo></msubsup></math> are also maximal matchings in the subgraph exposed so far. The following Lemma will be useful for the proof.

Claim 3.2

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mrow><msubsup><mi mathvariant="bold">N</mi><mi mathvariant="bold">G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">S</mi><mo stretchy="false">)</mo></mrow></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mrow></math> for some <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></math> . Then <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><msub><mi>M</mi><mi>u</mi></msub><mo stretchy="false">)</mo></mrow></math> , that is, u is exposed, after all the vertices in S are declared as vertices of V(M).

Proof

Observe that if there exists <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>x</mi><mo>&#8712;</mo><mi>S</mi></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>x</mi><mo>&#8713;</mo><mi>V</mi><mo stretchy="false">(</mo><msub><mi>M</mi><mi>u</mi></msub><mo stretchy="false">)</mo></mrow></math> , then after u is exposed, there exists <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>y</mi><mo>&#8712;</mo><msub><mi>N</mi><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>u</mi><mo stretchy="false">)</mo></mrow></mrow></math> such that (u, y) is present in <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi>M</mi><mi>u</mi><mo>&#8242;</mo></msubsup></math> . This implies <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><msubsup><mi>M</mi><mi>u</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow><mo>&#8838;</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mrow></math> , which is a contradiction to <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mrow><msubsup><mi mathvariant="bold">N</mi><mi mathvariant="bold">G</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">S</mi><mo stretchy="false">)</mo></mrow></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Now, we describe what our algorithm does when a vertex u is exposed. The complete pseudocode of our algorithm for Common Neighbor is given in Algorithm 1. When a vertex u is exposed in the stream, we try to extend the maximal matching <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>M</mi><mi>u</mi></msub></math> . Also, we store all the edges of the form (u, x) such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>x</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><msub><mi>M</mi><mi>u</mi></msub><mo stretchy="false">)</mo></mrow></math> , in a temporary memory T. As <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><msub><mi>M</mi><mi>u</mi></msub></mfenced><mo>&#8804;</mo><mi>K</mi></mrow></math> , we are storing <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mi>K</mi><mo stretchy="false">)</mo></mrow></math> many edges in T. Now, there are the following possibilities.

If <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><msubsup><mi>M</mi><mi>u</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow></math> , that is, either <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><msub><mi>M</mi><mi>u</mi></msub><mo stretchy="false">)</mo></mrow></math> or the matching <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>M</mi><mi>u</mi></msub></math> is extended by one of the edges stored in T, then we add all the edges stored in T to E(H).

Otherwise, for each <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><msub><mi>M</mi><mi>u</mi></msub><mo stretchy="false">)</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>S</mi></mfenced><mo>&#8804;</mo><mi>d</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>S</mi><mo>&#8838;</mo><msub><mi>N</mi><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>u</mi><mo stretchy="false">)</mo></mrow></mrow></math> , we check whether the number of common neighbors of the vertices present in S, that are already stored, is less than <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> . If yes, we add all the edges of the form (u, z) such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>z</mi><mo>&#8712;</mo><mi>S</mi></mrow></math> to E(H); else, we do nothing. Now, we reset T to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#8709;</mi></math> .

Now we argue about the space complexity of the algorithm. The set of edges in graph H is of two types: the edges between the vertices of V(M) are of the first type, and the edges with one vertex in V(M) and the other vertex in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>V</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></math> are of the second type. As <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>M</mi></mfenced><mo>&#8804;</mo><mi>K</mi></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mfenced><mo>&#8804;</mo><mn>2</mn><mi>K</mi></mrow></math> , the number of edges of the first type is at most <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mi>K</mi><mn>2</mn></msup><mo stretchy="false">)</mo></mrow></math> . To analyze the number of second type edges, note that each such edge e (along with at most other <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>-</mo><mn>1</mn></mrow></math> other edges) is added in Line 18 of Algorithm 1 only when there exist some <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>S</mi><mi>e</mi></msub><mo>&#8838;</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mrow></math> with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><msub><mi>S</mi><mi>e</mi></msub></mfenced><mo>&#8804;</mo><mi>d</mi></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>S</mi><mi>e</mi></msub></math> has less than <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#8467;</mi></math> common neighbors in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mi>N</mi><mi>H</mi><mo>&#8745;</mo></msubsup><mrow><mo stretchy="false">(</mo><msub><mi>S</mi><mi>e</mi></msub><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></mrow></math> . If we think of charging edge e to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>S</mi><mi>e</mi></msub></math> , then the number of edges charged to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>S</mi><mi>e</mi></msub></math> is at most <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>&#183;</mo><mi>&#8467;</mi></mrow></math> . So, the total number of the second type edges is at most <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mi>K</mi><mi>d</mi></msup><mo>&#183;</mo><mi>d</mi><mi>&#8467;</mi><mo stretchy="false">)</mo></mrow></math> . Putting things together the space complexity of Algorithm 1 is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mi>K</mi><mn>2</mn></msup><mo>+</mo><msup><mi>K</mi><mi>d</mi></msup><mo>&#183;</mo><mi>d</mi><mi>&#8467;</mi><mo stretchy="false">)</mo></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

We call our algorithm described in the proof of Lemma 3.1 and given in Algorithm 1, as <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="script">A</mi><mrow><mi mathvariant="italic">cn</mi></mrow></msub></math> . Lemma 3.3 justifies how the common neighbor subgraph of G (obtained by algorithm <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="script">A</mi><mrow><mi mathvariant="italic">cn</mi></mrow></msub></math> ) is important for the design and analysis of streaming algorithms for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion. Note that Lemma 3.3 is the central lemma of the paper and it says how common neighbor subgraphs may be of independent interest in the design of other parametrized (streaming) algorithms.

Lemma 3.3

Let G be a graph with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> and let F be a connected graph with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>d</mi><mo>&#8804;</mo><mi>K</mi></mrow></math> . Let H be the common neighbor subgraph of G with degree parameter d and common neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> , obtained by running the algorithm <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="script">A</mi><mrow><mi mathvariant="italic">cn</mi></mrow></msub></math> . Then the following holds in H: For any subset <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow></math> , where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">|</mo><mi>X</mi><mo stretchy="false">|</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> , F is a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> , such that F and <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> are isomorphic.

Proof

Let the common neighbor subgraph H, obtained by algorithm <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="script">A</mi><mrow><mi mathvariant="italic">cn</mi></mrow></msub></math> , contain a maximal matching M of G. First, observe that since <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> , the size of a subgraph F in G is at most dK. Now let us consider a subset <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">|</mo><mi>X</mi><mo stretchy="false">|</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> . First, suppose that <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is isomorphic to F. Then since H is a subgraph of G, <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is also a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> . Therefore, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>F</mi><mo>=</mo><msup><mi>F</mi><mo>&#8242;</mo></msup></mrow></math> and we are done.

Conversely, suppose F is a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> that is not a subgraph in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> . We show that there is a subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is isomorphic to F. Consider an arbitrary ordering <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">{</mo><msub><mi>e</mi><mn>1</mn></msub><mo>,</mo><msub><mi>e</mi><mn>2</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>e</mi><mi>s</mi></msub><mo stretchy="false">}</mo></mrow><mo>&#8838;</mo><mrow><mo stretchy="false">(</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow><mo stretchy="false">)</mo></mrow><mo>&#8745;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mrow></mrow></math> ; note that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>s</mi><mo>&#8804;</mo><mfenced close="|" open="|"><mi>E</mi><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mfenced></mrow></math> . We describe an iterative subroutine that converts the subgraph F to <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> through s steps, or equivalently, through a sequence of isomorphic subgraphs <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>F</mi><mn>0</mn></msub><mo>,</mo><msub><mi>F</mi><mn>1</mn></msub><mo>,</mo><msub><mi>F</mi><mn>2</mn></msub><mo>,</mo><mo>...</mo><msub><mi>F</mi><mi>s</mi></msub></mrow></math> in G such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>F</mi><mn>0</mn></msub><mo>=</mo><mi>F</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>F</mi><mi>s</mi></msub><mo>=</mo><msup><mi>F</mi><mo>&#8242;</mo></msup></mrow></math> .

Let us discuss the consequence of such an iterative routine. Just before the starting of step <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>s</mi><mo stretchy="false">]</mo></mrow></math> , we have the subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> is isomorphic to F and the set of edges in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow><mo stretchy="false">)</mo></mrow><mo>&#8745;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></mrow></math> is a subset of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><msub><mi>e</mi><mi>i</mi></msub><mo>,</mo><msub><mi>e</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>e</mi><mi>s</mi></msub><mo stretchy="false">}</mo></mrow></math> . In step i, we convert the subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> into <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> is isomorphic to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> . Just after the step <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>s</mi><mo stretchy="false">]</mo></mrow></math> , we have the subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> is isomorphic to F and the set of edges in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow><mo stretchy="false">)</mo></mrow><mo>&#8745;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>F</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></mrow></math> is a subset of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><msub><mi>e</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>e</mi><mrow><mi>i</mi><mo>+</mo><mn>2</mn></mrow></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>e</mi><mi>s</mi></msub><mo stretchy="false">}</mo></mrow></math> . In particular, in the end, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>F</mi><mi>s</mi></msub><mo>=</mo><msup><mi>F</mi><mo>&#8242;</mo></msup></mrow></math> is a subgraph both in G and H.

Now consider the instance just before step i. We show how we select the subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>e</mi><mi>i</mi></msub><mo>=</mo><mrow><mo stretchy="false">{</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo stretchy="false">}</mo></mrow></mrow></math> . Note that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>e</mi><mi>i</mi></msub><mo>&#8713;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow></mrow></math> . By the definition of the maximal matching M in G, it must be the case that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">|</mo><mo stretchy="false">{</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo stretchy="false">}</mo><mo>&#8745;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo><mo stretchy="false">|</mo><mo>&#8805;</mo><mn>1</mn></mrow></math> . From the construction of the common neighbor subgraph H, if both u and v are in V(M), then <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>e</mi><mi>i</mi></msub><mo>=</mo><mrow><mo stretchy="false">(</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow></mrow></math> . So, exactly one of u and v is present in V(M). Without loss of generality, let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>u</mi><mo>&#8712;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>M</mi><mo stretchy="false">)</mo></mrow></math> . Observe that v is a common neighbor of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> in G. Because of the maximality of M, each vertex in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> is present in V(M). Now, as <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">{</mo><mi>u</mi><mo>,</mo><mi>v</mi><mo stretchy="false">}</mo><mo>&#8713;</mo><mi>E</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow></math> , v is not a common neighbor of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>F</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow><mo>&#8834;</mo><msub><mi>N</mi><mi>G</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> in H. From the construction of the common neighbor subgraph, H contains at least <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> common neighbors of all the vertices present in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>F</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> as <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><msub><mi>N</mi><mi>F</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mfenced><mo>&#8804;</mo><mi>d</mi></mrow></math> . Of these common neighbors, at most <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> common neighbors can be vertices in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8746;</mo><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></mrow></math> . Thus, there is a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>v</mi><mo>&#8242;</mo></msup></math> (outside <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> ) such that it is a common neighbor of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>F</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> in H. Let <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> be the subgraph obtained by deleting vertex v from <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mrow><mi>i</mi><mo>-</mo><mn>1</mn></mrow></msub></math> and then adding vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>v</mi><mo>&#8242;</mo></msup></math> along with the edges between <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>v</mi><mo>&#8242;</mo></msup></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>N</mi><mi>F</mi></msub><mrow><mo stretchy="false">(</mo><mi>v</mi><mo stretchy="false">)</mo></mrow></mrow></math> . Observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> is a subgraph that is isomorphic to <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>F</mi><mi>i</mi></msub></math> . Moreover, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow><mo stretchy="false">)</mo></mrow><mo>&#8745;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><msub><mi>F</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow><mo>&#8838;</mo><mrow><mo stretchy="false">{</mo><msub><mi>e</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>e</mi><mrow><mi>i</mi><mo>+</mo><mn>3</mn></mrow></msub><mo>...</mo><mo>,</mo><msub><mi>e</mi><mi>s</mi></msub><mo stretchy="false">}</mo></mrow></mrow></math> . Thus, this leads to the fact that there is a subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> that is isomorphic to the subgraph F in <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Streamabality Results for F-Subgraph deletion and F-Minor deletion problems

Our result on Common Neighbor leads us to the following streamability result for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion.

Algorithm for F-Subgraph deletion

We first discuss the result on <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion, which is stated in the following theorem.

Theorem 4.1

<math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion parameterized by vertex cover size K is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi mathvariant="bold">d</mi><mn mathvariant="bold">2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi>d</mi><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> -streamable, where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>=</mo><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> .

Proof

Let (G, k, K) be an input for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion, where G is the input graph, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>&#8804;</mo><mi>K</mi></mrow></math> is the size of the solution of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion, and the parameter K is at least <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> .

Now, we describe the streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion. First, we run the Common Neighbor streaming algorithm described in Lemma 3.1 (and given in Algorithm 1) with degree parameter d and common neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> , and let the common neighbor subgraph obtained be H. We run a traditional FPT algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion [[10]] on H and output YES if and only if the output on H is YES.

Let us argue the correctness of this algorithm. By Lemma 3.3, for any subset <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>H</mi><mo stretchy="false">)</mo></mrow></math> , where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">|</mo><mi>X</mi><mo stretchy="false">|</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>F</mi><mo>&#8712;</mo><mi mathvariant="script">F</mi></mrow></math> is a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> , such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is isomorphic to <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> , is a subgraph of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> . In particular, let X be a k-sized vertex set of G. As mentioned before, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>&#8804;</mo><mi>K</mi></mrow></math> . Thus, by Lemma 3.3, X is a solution of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion in H if and only if X is a solution of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion in G. Therefore, we are done with the correctness of the streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion.

The streaming complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion is same as the streaming complexity for the algorithm <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="script">A</mi><mrow><mi mathvariant="italic">cn</mi></mrow></msub></math> from Lemma 3.1 with degree parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>=</mo><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow></math> and common neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> . Therefore, the streaming complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mi mathvariant="bold">d</mi><mn mathvariant="bold">2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi>d</mi><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Corollary 4.2

FVS, ECT, OCT and TD parameterized by vertex cover size K are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi>K</mi><mn>3</mn></msup><mo stretchy="false">)</mo></mrow></math> -streamable due to deterministic algorithms.

Algorithm for F-Minor deletion

Finally, we describe a streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion that works similar to that of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion due to the following proposition and the result is stated in Theorem 4.4.

Proposition 4.3

([[15]]) Let G be a graph with F as a minor and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> . Then there exists a subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>G</mi><mo>&#8727;</mo></msup></math> of G that has F as a minor such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><msup><mi>G</mi><mo>&#8727;</mo></msup><mo stretchy="false">)</mo></mrow><mo>&#8804;</mo><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mrow></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mfenced close="|" open="|"><mi>V</mi><mo stretchy="false">(</mo><msup><mi>G</mi><mo>&#8727;</mo></msup><mo stretchy="false">)</mo></mfenced><mo>&#8804;</mo><mfenced close="|" open="|"><mi>V</mi><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mfenced><mo>+</mo><mi>K</mi><mrow><mo stretchy="false">(</mo><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mrow><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><mo>.</mo></mrow></math>

Theorem 4.4

<math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion parameterized by vertex cover size K are <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><msup><mi mathvariant="bold">d</mi><mn mathvariant="bold">2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi>d</mi><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> -streamable, where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>=</mo><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> .

Proof

Let (G, k, K) be an input for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion, where G is the input graph, k is the size of the solution of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion we are looking for, and the parameter K is such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> . Note that, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>&#8804;</mo><mi>K</mi></mrow></math> .

Now, we describe the streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion. First, we run the Common Neighbor streaming algorithm described in Lemma 3.1 with degree parameter d and common neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> , and let the common neighbor subgraph obtained be H. We run a traditional FPT algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion [[10]] and output YES if and only if the output on H is YES.

Let us argue the correctness of this algorithm, that is, we prove the following for any <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>F</mi><mo>&#8712;</mo><mi mathvariant="script">F</mi></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains F as a minor if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> as a minor such that F and <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> are isomorphic, where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>X</mi><mo>&#8838;</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></math> is of size at most K. For the only if part, suppose <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> as a minor. Then since H is a subgraph of G, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> as a minor. For the if part, let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains F as a minor. By Proposition 4.3, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>G</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains a subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>G</mi><mrow><mrow /><mo>&#8727;</mo></mrow></msup></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>G</mi><mo>&#8727;</mo></msup></math> contains F as a minor and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><msup><mi>G</mi><mo>&#8727;</mo></msup><mo stretchy="false">)</mo></mrow><mo>&#8804;</mo><mi mathvariant="normal">&#916;</mi><mrow><mo stretchy="false">(</mo><mi>F</mi><mo stretchy="false">)</mo></mrow></mrow></math> . Now, Lemma 3.3 implies that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> also contains a subgraph <math xmlns="http://www.w3.org/1998/Math/MathML"><mover accent="true"><msup><mi>G</mi><mo>&#8727;</mo></msup><mo stretchy="false">^</mo></mover></math> that is isomorphic to <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>G</mi><mo>&#8727;</mo></msup></math> . Hence, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>H</mi><mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo><mi>X</mi></mrow></math> contains <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> as a minor such that <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>F</mi><mo>&#8242;</mo></msup></math> is isomorphic to F.

The streaming complexity of the streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion is same as the streaming complexity for the algorithm <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="script">A</mi><mrow><mi mathvariant="italic">cn</mi></mrow></msub></math> from Lemma 3.1 with degree parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>d</mi><mo>=</mo><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi mathvariant="script">F</mi><mo stretchy="false">)</mo></mrow></math> and common neighbor parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>d</mi><mo>+</mo><mn>2</mn><mo stretchy="false">)</mo><mi>K</mi></mrow></math> . Therefore, the streaming complexity for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><msup><mi>d</mi><mn>2</mn></msup><mo>&#183;</mo><msup><mi>K</mi><mrow><mi>d</mi><mo>+</mo><mn>1</mn></mrow></msup><mo stretchy="false">)</mo></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Lower Bounds

Before we explicitly give the statements of the stated lower bound results presented in Table 1, we want to note that a lower bound on Feedback Vertex Set is also a lower bound for <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Subgraph deletion (deletion of cycles as subgraphs) and <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">F</mi></math> -Minor deletion (deletion of 3-cycles as minors). Observe that we will be done by proving the following theorems, and the rest of the lower bound results will follow from Observations 2.4 and 2.5.

Theorem 5.1

Feedback Vertex Set, Even Cycle Transversal and Odd Cycle Transversal are

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard parameterized by solution size k and even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> ,

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard parameterized by solution size k and even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard parameterized by vertex cover size K and even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> .

Theorem 5.2

TD is

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard parameterized by solution size k and even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> ,

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard parameterized by solution size k and even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard parameterized by vertex cover size K and even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> .

Remark 2

The proofs of part (I) of Theorems 5.1 and 5.2 use the lower bound constructions given in [[30]]. To the best of our knowledge this is the first set of results on hardness in the Al model.

The proofs of parts (II) and (III) of Theorems 5.1 and 5.2 use the lower bound constructions given in [[7]].

In Section 5.1 we will briefly describe the different results from communication complexity we will be using in this section. In Section 5.2 we will give the details of the proofs of Theorems 5.1 and 5.2.

Communication Complexity Results

Lower bounds of communication complexity have been used to provide lower bounds for the streaming complexity of problems. In Yao's two party communication model, Alice and Bob get inputs and the objective is to compute a function of their inputs with minimum bits of communication. In one way communication, only Alice is allowed to send messages and Bob produces the final output; whereas in two way communication both Alice and Bob can send messages.

Definition 5.3

The one (two) way communication complexity of a problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is the minimum number of bits that must be sent by Alice to Bob (exchanged between Alice and Bob) to solve <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> on any arbitrary input with success probability 2/3.

The following problems are very fundamental problems in communication complexity and we use these problems in showing lower bounds on the streaming complexity of problems considered in this paper.

<bold> _HT_ <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Index</mtext><mi>n</mi></msub></mrow></math> _ht_ : Alice gets as input _HT_ <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">x</mi><mo>∈</mo><msup><mrow><mo stretchy="false">{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">}</mo></mrow><mi>n</mi></msup></mrow></math> _ht_ and Bob has an index _HT_ <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>∈</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> _ht_ . Bob wants to determine whether _B_x</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mrow /><mi>j</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . Formally, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Index</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="bold">x</mi><mi>j</mi></msub><mo>=</mo><mn>1</mn></mrow></math> and 0, otherwise.

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> : Alice and Bob get inputs <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo>&#8712;</mo><msup><mrow><mo stretchy="false">{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo stretchy="false">}</mo></mrow><mi>n</mi></msup></mrow></math> , respectively. The objective is to decide whether there exists an <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . Formally, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> (x, y) <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo>=</mo><mn>0</mn></mrow></math> if there exists an <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> and 1, otherwise.

<math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> [[30]] : Alice gets a permutation <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#960;</mi><mo>:</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo stretchy="false">&#8594;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> and Bob gets an index <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> . The objective of Bob is to decide the value of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#960;</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo></mrow></math> , defined as the j-th bit in the string of 0's and 1's obtained by concatenating the bit expansions of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>...</mo><mi>&#960;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> . In other words, let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#934;</mi><mo>:</mo><mo stretchy="false">[</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">]</mo><mo stretchy="false">&#8594;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo>&#215;</mo><mo stretchy="false">[</mo><mo>log</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> be a bijective function defined as

<math display="block" xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#934;</mi><mrow><mo stretchy="false">(</mo><mi>j</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mfenced close=")" open="("><mrow><mo>&#8968;</mo><mfrac><mi>j</mi><mrow><mo>log</mo><mi>n</mi></mrow></mfrac><mo>&#8969;</mo></mrow><mo>,</mo><mi>j</mi><mo>+</mo><mo>log</mo><mi>n</mi><mo>-</mo><mrow><mo>&#8968;</mo><mfrac><mi>j</mi><mrow><mo>log</mo><mi>n</mi></mrow></mfrac><mo>&#8969;</mo></mrow><mo>&#215;</mo><mo>log</mo><mi>n</mi></mfenced><mo>.</mo></mrow></math>

Graph

For a permutation <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#960;</mi><mo>:</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo><mo stretchy="false">&#8594;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> , Bob needs to determine the value of the <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#947;</mi></math> -th bit of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#960;</mi><mfenced close=")" open="("><mo>&#8968;</mo><mfrac><mi>j</mi><mrow><mo>log</mo><mi>n</mi></mrow></mfrac><mo>&#8969;</mo></mfenced></mrow></math> , where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#947;</mi><mo>=</mo><mfenced close=")" open="("><mi>j</mi><mo>+</mo><mo>log</mo><mi>n</mi><mo>-</mo><mo>&#8968;</mo><mfrac><mi>j</mi><mrow><mo>log</mo><mi>n</mi></mrow></mfrac><mo>&#8969;</mo><mo>&#215;</mo><mo>log</mo><mi>n</mi></mfenced></mrow></math> .

Proposition 5.4

([[22], [30]])

The one way communication complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Index</mtext><mi>n</mi></msub></mrow></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> .

The two way communication complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> .

The one way communication complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#937;</mi><mo stretchy="false">(</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> .

<bold>A note on reduction from</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Index</mtext><mi>n</mi></msub></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> : A reduction from a problem <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="normal">&#928;</mi><mn>1</mn></msub></math> in one/two way communication complexity to a problem <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="normal">&#928;</mi><mn>2</mn></msub></math> in streaming algorithms is typically as follows: The two players Alice and Bob device a communication protocol for <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="normal">&#928;</mi><mn>1</mn></msub></math> that uses a streaming algorithm for <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="normal">&#928;</mi><mn>2</mn></msub></math> as a subroutine. Typically in a round of communication, a player gives inputs to the input stream of the streaming algorithm, obtains the compact sketch produced by the streaming algorithm and communicates this sketch to the other player. This implies that a lower bound on the communication complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="normal">&#928;</mi><mn>1</mn></msub></math> also gives a lower bound on the streaming complexity of <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi mathvariant="normal">&#928;</mi><mn>2</mn></msub></math> .

The following Proposition summarizes a few important consequences of reductions from problems in communication complexity to problems for streaming algorithms:

Proposition 5.5

If we can show a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Index</mtext><mi>n</mi></msub></mrow></math> to a problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> such that the reduction uses a 1-pass streaming algorithm of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> as a subroutine, then <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard.

If we can show a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> to a problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> such that the reduction uses a 1-pass streaming algorithm of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> as a subroutine, then <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard, for any <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>p</mi><mo>&#8712;</mo><mi mathvariant="double-struck">N</mi></mrow></math> [[2], [4], [6]].

If we can show a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> to a problem <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> in model <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">M</mi></math> such that the reduction uses a 1-pass streaming algorithm of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> as a subroutine, then <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="normal">&#928;</mi></math> is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi mathvariant="script">M</mi><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard.

Proofs of Theorems 5.1 and 5.2

Proof of Theorems

5.1 The proofs for all three problems are similar. We first consider Feedback Vertex Set. To begin with, we show the hardness results of FVS for solution size <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> .

Proof of Theorems

5.1 (I) We give a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> to FVS in the Al model when the solution size parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . The idea is to build a graph G with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> and construct edges according to the input of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> , such that the output of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> is 0 if and only if G is cycle-free.

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> be a one pass streaming algorithm that solves FVS in Al model using <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>o</mi><mo stretchy="false">(</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> space. Let G be a graph with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>4</mn><mi>n</mi><mo>+</mo><mn>2</mn></mrow></math> vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mi>n</mi></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>,</mo><msubsup><mi>u</mi><mn>1</mn><mo>&#8242;</mo></msubsup><mo>,</mo><mo>&#8943;</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mi>u</mi><mi>n</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msubsup><mi>v</mi><mn>1</mn><mo>&#8242;</mo></msubsup><mo>,</mo><mo>&#8943;</mo><mo>,</mo><msubsup><mi>v</mi><mi>n</mi><mo>&#8242;</mo></msubsup><mo>,</mo><mi>w</mi><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>w</mi><mo>&#8242;</mo></msup></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#960;</mi></math> be the input of Alice for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> . See Fig. 2 for an illustration.

<bold>Alice's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Alice inputs the graph G first by exposing the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mi>n</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>n</mi></msub></math> , sequentially. (i) While exposing the vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>i</mi></msub></math> , Alice gives as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>i</mi></msub><mo>,</mo><msubsup><mi>u</mi><mi>i</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow><mo>,</mo><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>i</mi></msub><mo>,</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow></msub><mo stretchy="false">)</mo></mrow></mrow></math> ; (ii) while exposing the vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>i</mi></msub></math> , Alice gives the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msubsup><mi>v</mi><mi>i</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow><mrow><mo>,</mo><mo stretchy="false">(</mo></mrow><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mrow><msup><mi>&#960;</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mrow><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow></mrow></msub><mrow><mo stretchy="false">)</mo></mrow></mrow></math> to the input stream of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> .

After the exposure of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mi>n</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>n</mi></msub></math> as per the Al model, Alice sends the current memory state of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , i.e the sketch generated by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , to Bob. Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> be the input of Bob and let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#968;</mi><mo>,</mo><mi>&#947;</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">&#934;</mi><mo stretchy="false">(</mo><mi>j</mi><mo stretchy="false">)</mo></mrow></math> .

<bold>Bob's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Bob exposes the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mi>u</mi><mn>1</mn><mo>&#8242;</mo></msubsup><mo>&#8943;</mo><mo>,</mo><msubsup><mi>u</mi><mi>n</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msubsup><mi>v</mi><mn>1</mn><mo>&#8242;</mo></msubsup><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo>...</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msubsup><mi>v</mi><mi>n</mi><mo>&#8242;</mo></msubsup><mo>,</mo><mi>w</mi><mo>,</mo><msup><mi>w</mi><mo>&#8242;</mo></msup></mrow></math> , sequentially. (i) While exposing a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi>u</mi><mi>i</mi><mo>&#8242;</mo></msubsup></math> where <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8800;</mo><mi>&#968;</mi></mrow></math> , Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>u</mi><mi>i</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msub><mi>u</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> to the input stream of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> ; (ii) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup></math> , Bob gives the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo stretchy="false">)</mo></mrow></math> ; (iii) while exposing a vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msubsup><mi>v</mi><mi>i</mi><mo>&#8242;</mo></msubsup></math> , Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>v</mi><mi>i</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> , and the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>v</mi><mi>i</mi><mo>&#8242;</mo></msubsup><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>bit</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>&#947;</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> ; (iv) while exposing w, Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo stretchy="false">)</mo></mrow></math> , and the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msubsup><mi>v</mi><mi>i</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>bit</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>&#947;</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> ; (v) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mi>w</mi><mo>&#8242;</mo></msup></math> , Bob gives the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo>,</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow></math> .

Observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> . Now we show that the output of FVS is NO if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#960;</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> . Recall that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> .

From the construction, observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo stretchy="false">)</mo></mrow><mo>,</mo><mrow><mo stretchy="false">(</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo>,</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow><mo>,</mo><mrow><mo stretchy="false">(</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo stretchy="false">)</mo></mrow><mo>,</mo><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo>,</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo stretchy="false">)</mo></mrow><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo>,</mo><msubsup><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> . When <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#960;</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> , the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow><mo>&#8242;</mo></msubsup><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow></math> is present in G. So, G contains the cycle <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo>,</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>&#968;</mi></msub><mo>,</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo>,</mo><msubsup><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow><mo>&#8242;</mo></msubsup><mrow><mo stretchy="false">)</mo></mrow></mrow></math> , that is, the output of FVS is NO.

On the other hand, if the output of FVS is NO, then there is a cycle in G. From the construction, the cycle is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msup><mi>w</mi><mo>&#8242;</mo></msup><mo>,</mo><msubsup><mi>u</mi><mi>&#968;</mi><mo>&#8242;</mo></msubsup><mo>,</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo>,</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo>,</mo><msubsup><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow><mo>&#8242;</mo></msubsup><mo stretchy="false">)</mo></mrow></math> . As <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msubsup><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow><mo>&#8242;</mo></msubsup><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow></math> is an edge, the <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#947;</mi></math> -th bit of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></math> is 1, that is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#960;</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> . Now by Propositions 5.4 and 5.5(iii), we obtain that Feedback Vertex Set is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> and when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Graph: Fig. 2Illustration of Proof of Theorem 5.1 (I). Consider n=4. Let π:[4]→[4] such that π(1)=3,π(2)=4,π(3)=2 and π(4)=1. So the concatenated bit string is 110010012. In (a), j=5 , Φ(j)=(ψ,γ)=(3,1) , Permn(π,j)=1 , and G contains a cycle. In (b), j=4 , Φ(j)=(ψ,γ)=(2,2) , Permn(π,j)=0 , and G does not contain a cycle. Recall that we take n as a power of 2. For 1≤i≤n-1 , the bit expansion of i is the usual bit notation of i using log2n bits; the bit expansion of n is log2n many consecutive zeros. For example: Take n=32. The bit expansion of 32 is 100000. We ignore the bit 1 and say that the bit expansion of 32 is 00000

Graph: Fig. 3Illustration of Proof of Theorem 5.1 (II). Consider n=4. In (a), x=1001 and y=0100 , that is, Disjn (x, y) =1 , and G does not contain a cycle. In (b), x=1100 and y=0110 , that is, Disjn (x, y) =0 , and G contains a cycle

Proof of Theorems

5.1 (II) We give a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> to FVS in the Al model when the solution size parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . The idea is to build a graph G with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> and construct edges according to the input of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> , such that the output of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> is 1 if and only if G is cycle-free.

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> be a one pass streaming algorithm that solves FVS in Al model, such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and the space used is o(n). Let G be a graph with 4n vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>11</mn></msub><mo>,</mo><msub><mi>u</mi><mn>12</mn></msub><mo>,</mo><msub><mi>u</mi><mn>13</mn></msub><mo>,</mo><msub><mi>u</mi><mn>14</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>1</mn></mrow></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mrow><mi>n</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>4</mn></mrow></msub></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi></mrow></math> be the input of Alice and Bob for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> , respectively. See Fig. 3 for an illustration.

<bold>Alice's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Alice inputs the graph G by exposing the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>11</mn></msub><mo>,</mo><msub><mi>u</mi><mn>12</mn></msub><mo>,</mo><msub><mi>u</mi><mn>21</mn></msub><mo>,</mo><msub><mi>u</mi><mn>22</mn></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo>...</mo><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>1</mn></mrow></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>n</mi><mn>2</mn></mrow></msub></math> , sequentially. (i) While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub></math> , Alice gives as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> . Also, Alice gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> ; (ii) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub></math> , Alice gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> . Also, Alice gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

After the exposure of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>11</mn></msub><mo>,</mo><msub><mi>u</mi><mn>12</mn></msub><mo>,</mo><msub><mi>u</mi><mn>21</mn></msub><mo>,</mo><msub><mi>u</mi><mn>22</mn></msub><mo>...</mo><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>1</mn></mrow></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>n</mi><mn>2</mn></mrow></msub></math> as per the Al model, Alice sends current memory state of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , i.e. the sketch generated by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , to Bob.

<bold>Bob's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Bob exposes the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>13</mn></msub><mo>,</mo><msub><mi>u</mi><mn>14</mn></msub><mo>,</mo><msub><mi>u</mi><mn>23</mn></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>24</mn></msub><mo>...</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mrow><mi>n</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>4</mn></mrow></msub></mrow></math> sequentially. (i) While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub></math> , Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , and gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> ; (ii) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub></math> , Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , and gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

Observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mn>4</mn></mrow></math> . Recall that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . Now we show that the output of FVS is NO if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

From the construction, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo stretchy="false">)</mo></mrow><mo>,</mo><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> , for each <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> . If <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> , there exists <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . This implies the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> are present in G. So, the cycle <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> is present in G, that is, the output of FVS is NO.

Conversely, if the output of FVS is NO, there exists a cycle in G. From the construction, the cycle must be <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mrow><mo stretchy="false">)</mo></mrow></mrow></math> for some <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> . As the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>4</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> are present in G, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> , that is, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

Now by Propositions 5.4 and 5.5(ii), we obtain that Feedback Vertex Set is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">A</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">L</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> and when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Proof of Theorems

5.1 (III) We give a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> to FVS in the Va model when the solution size parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . The idea is to build a graph G with vertex cover size bounded by K and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and construct edges according to the input of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> , such that the output of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> is 1 if and only if G is cycle-free.

Graph: Fig. 4Illustration of Proof of Theorem 5.1 (III). Consider n=4. In (a), x=1000 and y=0101 , that is, Disjn(x,y)=1 , and G does not contain a cycle. In (b), x=0011 and y=1010 , that is, Disjn(x,y)=0 , and G contains a cycle

Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> be a one pass streaming algorithm that solves FVS in Va model, such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mi>K</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> , and the space used is o(n). Let G be a graph with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>+</mo><mn>3</mn></mrow></math> vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><mi>w</mi></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi></mrow></math> be the input of Alice and Bob for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> , respectively. See Fig. 4 for an illustration.

<bold>Alice's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Alice inputs the graph G first by exposing the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></math> , sequentially. (i) While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>a</mi></msub></math> , Alice does not give any edge; (ii) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>i</mi></msub></math> , Alice gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow></math> , as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

After the exposure of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></math> as per Va model, Alice sends the current memory state of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , i.e., the sketch generated by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , to Bob.

<bold>Bob's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Bob first exposes <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>b</mi></msub></math> and then exposes w. (i) While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>b</mi></msub></math> , Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> ; (ii) while exposing w, Bob gives the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub><mo stretchy="false">)</mo></mrow></math> , as inputs to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> .

From the construction, observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mn>2</mn><mo>&#8804;</mo><mi>K</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> . Recall that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> .

Now we show that the output of FVS is NO if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

From the construction, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow><mo>,</mo><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> . If <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> , there exists <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . This implies the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> are present in G. So, the cycle <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow></math> is present in G, that is, the output of FVS is NO.

Conversely, if the output of FVS is NO, there exists a cycle in G. From the construction, the cycle must be <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="script">C</mi><mo stretchy="false">(</mo><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub><mrow><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow></mrow></math> for some <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> . As the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> are present in G, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> , that is, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

Now by Propositions 5.4 and 5.5(ii), we obtain that Feedback Vertex Set parameterized by vertex cover size K is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> , and when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

In each of the above three cases, we can make the reduction work for any k, by adding k many vertex disjoint cycles of length 4, i.e. <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>C</mi><mn>4</mn></msub></math> 's, to G. In Theorem 5.1 (III), the vertex cover must be bounded. In the given reduction for Theorem 5.1 (III), the vertex cover of the constructed graph is at most 2. Note that by the addition of k many edge disjoint <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>C</mi><mn>4</mn></msub></math> 's, the vertex cover of the constructed graph in the modified reduction is at most <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>2</mn></mrow></math> , and is therefore still a parameter independent of the input instance size.

This completes the proof of the Theorem 5.1 with respect to FVS.

If the graph constructed in the reduction, in any of the above three cases for Feedback Vertex Set, contains a cycle, then it is of even length. Otherwise, the graph is cycle free. Hence, the proof of this Theorem with respect to ECT is same as the proof for FVS.

Similarly, a slight modification can be made to the constructed graph, in all three of the above cases, such that a cycle in the graph is of odd length if a cycle exists. Thereby, the proof of this Theorem with respect to OCT also is very similar to the proof for FVS. <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Proof of Theorems

5.2 We first show the hardness results of TD for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> in all three cases.

Graph: Fig. 5Illustration of Proof of Theorem 5.2 (I). Consider n=4. Let π:[4]→[4] such that π(1)=3,π(2)=4,π(3)=2 , and π(4)=1. So the concatenated bit string is 11001001. In (a), j=5 , Φ(j)=(ψ,γ)=(3,1) , Permn(π,j)=1 and G contains a triangle. In (b), j=4 , Φ(j)=(ψ,γ)=(2,2) , Permn(π,j)=0 , and G does not contain any triangle

Proof of Theorems

5.2 (I) We give a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> to TD when the solution size parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> be a one pass streaming algorithm that solves TD in Va model, such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> , and the space used is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>o</mi><mo stretchy="false">(</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> .

Let G be a graph with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>2</mn><mi>n</mi><mo>+</mo><mn>1</mn></mrow></math> vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mi>n</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>,</mo><mi>w</mi></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#960;</mi></math> be the input of Alice for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> . See Fig. 5 for an illustration.

<bold>Alice's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Alice inputs the graph G by exposing the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mi>n</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo>...</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>n</mi></msub></math> , sequentially. (i) While exposing the vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>i</mi></msub></math> , Alice does not give any edge; (ii) while exposing the vertex <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>i</mi></msub></math> , Alice gives the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo></mrow></msub><mo>,</mo><msub><mi>u</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> as an input to the stream of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> .

After the exposure of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mi>n</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>n</mi></msub></math> as per the Va model, Alice sends the current memory state of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , i.e. the sketch generated by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , to Bob. Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>j</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> be the input of Bob and let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#968;</mi><mo>,</mo><mi>&#947;</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="normal">&#934;</mi><mo stretchy="false">(</mo><mi>j</mi><mo stretchy="false">)</mo></mrow></math> .

<bold>Bob's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Bob exposes only the vertex w. Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo stretchy="false">)</mo></mrow></math> , and the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>bit</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>i</mi><mo>,</mo><mi>&#947;</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> , as input to the stream of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> .

From the construction, note that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> . Recall that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . Now we show that, the output of TD is NO if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#960;</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> .

From the construction, the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo>,</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>w</mi><mo>,</mo><msub><mi>u</mi><mi>&#968;</mi></msub><mo stretchy="false">)</mo></mrow></math> are present in G. If <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>x</mi><mi>y</mi><mo>=</mo><mn>1</mn></mrow></math> , then <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> . So, there exists a triangle in G, that is, the output of TD is NO.

On the other hand, if the output of TD is NO, then there exists a triangle in G. From the construction, the triangle is formed with the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>&#968;</mi></msub><mo>,</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub></mrow></math> and w. As <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></msub><mo>,</mo><mi>w</mi><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> , the <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>&#947;</mi></math> -th bit of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>&#960;</mi><mo stretchy="false">(</mo><mi>&#968;</mi><mo stretchy="false">)</mo></mrow></math> is 1, that is, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Perm</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mi>&#960;</mi><mo>,</mo><mi>j</mi><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn></mrow></math> .

Now by Propositions 5.4 and 5.5(iii), we obtain that TD is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo>log</mo><mi>n</mi><mo stretchy="false">)</mo></mrow></math> -hard even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> , and when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Graph: Fig. 6Illustration of Proof of Theorem 5.2 (II). Consider n=4. In (a), x=1001 and y=0100 , that is, Disjn(x,y)=1 , and G does not contain any triangle. In (b), x=0110 and y=1010 , that is, Disjn(x,y)=0 , and G contains a triangle

Proof of Theorems

5.2 (II) We give a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> to TD when the solution size parameter <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> be a one pass streaming algorithm that solves TD in Va model, such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and the space used is o(n). Let G be a graph with 3n vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>11</mn></msub><mo>,</mo><msub><mi>u</mi><mn>12</mn></msub><mo>,</mo><msub><mi>u</mi><mn>13</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>3</mn></mrow></msub></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi></mrow></math> be the input of Alice and Bob for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> . See Fig. 6 for an illustration.

<bold>Alice's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Alice inputs the graph G first by exposing the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mn>11</mn></msub></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mn>12</mn></msub></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mn>21</mn></msub></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mn>22</mn></msub></math> ,..., <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>n</mi><mn>1</mn></mrow></msub></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>n</mi><mn>2</mn></mrow></msub></math> , sequentially. (i) While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub></math> , Alice does not give any edge; (ii) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub></math> , Alice gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> , if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> , as inputs to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> .

After the exposure of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>11</mn></msub><mo>,</mo><msub><mi>u</mi><mn>12</mn></msub><mo>,</mo><msub><mi>u</mi><mn>21</mn></msub><mo>,</mo><msub><mi>u</mi><mn>22</mn></msub><mo>...</mo><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>1</mn></mrow></msub><mo>,</mo></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>n</mi><mn>2</mn></mrow></msub></math> as per the Va model, Alice sends current memory state of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , i.e. the sketch generated by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , to Bob.

<bold>Bob's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Bob exposes the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mn>13</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>u</mi><mrow><mi>n</mi><mn>3</mn></mrow></msub></mrow></math> , sequentially. While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub></math> , Bob gives the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> as two inputs to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

From the construction, note that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mn>2</mn></mrow></math> . Recall that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . Now we show that the output of TD is NO if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

If <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> , there exists <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . From the construction, the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> are present in G. So, there exists a triangle in G, that is, the output of TD is NO.

Conversely, if the output of TD is NO, there exists a triangle in G. From the construction, the triangle is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> for some <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> . As the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> , <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> ; and as the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>1</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>3</mn></mrow></msub><mo>,</mo><msub><mi>u</mi><mrow><mi>i</mi><mn>2</mn></mrow></msub><mo stretchy="false">)</mo></mrow></math> are in G, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . So, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

Now by Propositions 5.4 and 5.5(ii), we obtain that TD is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="normal">&#916;</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>=</mo><mi mathvariant="script">O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></math> , and when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Graph: Fig. 7Illustration of Proof of Theorem 5.2 (III). Consider n=4. In (a), x=1000 and y=0101 , that is, Disjn(x,y)=1 , and G does not contain any triangle. In (b), x=0011 and y=1010 , that is, Disjn(x,y)=0 , and G contains a triangle

Proof of Theorems

5.2 (III) We give a reduction from <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> to TD parameterized by vertex cover size K, where <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> is a one pass streaming algorithm that solves TD parameterized by K in Va model such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> , and the space used is o(n). Let G be a graph with <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>n</mi><mo>+</mo><mn>2</mn></mrow></math> vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub></mrow></math> . Let <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi></mrow></math> be the input of Alice and Bob for <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> . See Fig. 7 for an illustration.

<bold>Alice's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Alice inputs the graph G first by exposing the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></math> sequentially. (i) While exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>a</mi></msub></math> , Alice does not give any edge; (ii) while exposing <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>i</mi></msub></math> , Alice gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

After the exposure of <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><mo>...</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub></mrow></math> as per the Va model, Alice sends current memory state of <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , i.e. the sketch generated by <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> , to Bob.

<bold>Bob's input to</bold> <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> : Bob exposes <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>u</mi><mi>b</mi></msub></math> only. Bob gives the edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow></math> unconditionally, and an edge <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> as input to <math xmlns="http://www.w3.org/1998/Math/MathML"><mi mathvariant="script">A</mi></math> if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

From the construction, observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><mtext>VC</mtext><mspace width="0.333333em" /><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>&#8804;</mo><mn>2</mn><mo>&#8804;</mo><mi>K</mi></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> . Recall that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> .

Now we show that the output of TD is NO if and only if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

Observe that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> . If <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> , there exists an <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>i</mi><mo>&#8712;</mo><mo stretchy="false">[</mo><mi>n</mi><mo stretchy="false">]</mo></mrow></math> such that <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> .

From the construction, the edges <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><msub><mi>u</mi><mi>b</mi></msub><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo stretchy="false">)</mo></mrow></math> are present in G. So, G contains the triangle with vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub></mrow></math> and w, i.e., the output of TD is NO.

On the other hand, if the output of TD is NO, there exists a triangle in G. From the construction, the triangle is formed with the vertices <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>u</mi><mi>a</mi></msub><mo>,</mo><msub><mi>u</mi><mi>b</mi></msub></mrow></math> and <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>v</mi><mi>i</mi></msub></math> . As <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> implies <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>x</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> , and <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><msub><mi>v</mi><mi>i</mi></msub><mo>,</mo><msub><mi>u</mi><mi>a</mi></msub><mo stretchy="false">)</mo></mrow><mo>&#8712;</mo><mi>E</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow></mrow></math> implies <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi>y</mi><mi>i</mi></msub><mo>=</mo><mn>1</mn></mrow></math> . So, <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mspace width="0.333333em" /><msub><mtext>Disj</mtext><mi>n</mi></msub></mrow></math> <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo stretchy="false">(</mo><mi mathvariant="bold">x</mi><mo>,</mo><mi mathvariant="bold">y</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mn>0</mn></mrow></math> .

Now by Propositions 5.4 and 5.5(ii), we obtain that TD parameterized by vertex cover size K is <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mo stretchy="false">(</mo><mrow><mi mathvariant="normal">V</mi><mstyle mathsize="0.6em"><mi mathvariant="normal">A</mi></mstyle></mrow><mo>,</mo><mi>n</mi><mo stretchy="false">/</mo><mi>p</mi><mo>,</mo><mi>p</mi><mo stretchy="false">)</mo></mrow></math> -hard even if <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><msub><mi mathvariant="normal">&#916;</mi><mrow><mi mathvariant="italic">av</mi></mrow></msub><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi mathvariant="script">O</mi><mrow><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow></mrow></math> , and when <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mi>k</mi><mo>=</mo><mn>0</mn></mrow></math> . <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

In each of the above cases, we can make the reductions work for any k, by adding k many vertex disjoint triangles to G. In Theorem 5.2 (III), the vertex cover must be bounded. In the given reduction for Theorem 5.2 (III), the vertex cover of the constructed graph is at most 2. Note that by the addition of k many edge disjoint <math xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>C</mi><mn>4</mn></msub></math> 's, the vertex cover of the constructed graph in the modified reduction is at most <math xmlns="http://www.w3.org/1998/Math/MathML"><mrow><mn>2</mn><mi>k</mi><mo>+</mo><mn>2</mn></mrow></math> , and is therefore still a parameter independent of the input instance size.

Hence, we are done with the proof of the Theorem 5.2. <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>&#9633;</mo></math>

Conclusion

In this paper, we initiate the study of parameterized streaming complexity with structural parameters for graph deletion problems. Our study also compares the parameterized streaming complexity of several graph deletion problems in the different streaming models. In future, a natural question is to investigate why such a classification exists for seemingly similar graph deletion problems, and conduct a systematic study of other graph deletion problems as well.

Appendix

A Problem Definitions

In this Section we define the following problems formally.

Graph

Graph

Graph

Graph

Graph

Graph

Graph

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

By Arijit Bishnu; Arijit Ghosh; Sudeshna Kolay; Gopinath Mishra and Saket Saurabh

Reported by Author; Author; Author; Author; Author