<p><strong>Restricted</strong> <strong>$k$-set</strong> <strong>cover</strong>:</p>

<p><strong>Input:</strong> $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$.</p>

<p><strong>Output:</strong> $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\},
i_1=min(S_1),i_2=min(S_1\cap S_{i_1}), \cdots, i_k=min(S_1\cap S_{i_2}\cap\cdots\cap S_{i_{k-1}})$</p>

<p>This problem is <strong>Restricted</strong> <strong>$k$-set</strong> <strong>cover</strong> 
I want to know the above problem is in <strong>L</strong> or <strong>NL</strong>?</p>

<p>I trying to show this problem is in <strong>NL</strong>-complete. But I did not get  any problem which is <strong>NL</strong>-complete connects to this problem.   </p>

CC BY-SA 3.0
2017-06-02T02:44:57.757Z
[Check this out.][1] 


  [1]: https://books.google.com/books?id=_qptCQAAQBAJ&pg=PA667&lpg=PA667&dq=%22restricted%20set%20cover%22&source=bl&ots=XbZuStphxm&sig=pm89fCeZrqxtVcJnItgeljKZPjw&hl=en&sa=X&ved=0ahUKEwjO47vWj57UAhVDSyYKHQYLBfQQ6AEIJzAA#v=onepage&q=%22restricted%20set%20cover%22&f=false
Tayfun Pay
CC BY-SA 3.0
2017-06-02T04:45:57.947Z
@TayfunPay their (given ref) definition of restricted $k$-set cover different from this definition. Even in their [original paper](http://cglab.ca/~morin/publications/fpt/covering-dcg.pdf) definition of restricted $k$-set cover no existence.
GOLD
CC BY-SA 3.0
2017-06-02T15:14:14.210Z
Can you explain yours with an example?
Tayfun Pay
CC BY-SA 3.0
2017-06-03T07:31:26.093Z
So it seems that when you're checking for membership in each $S_{i_j}$, you need to keep all $i_{p < j}$. For this reason, its not straightforward why it would be in $L$, let alone $NL$.. Cool problem though, it feels like one of these ones which would have the same parallel lower bound as sequential.
Samuel Schlesinger
CC BY-SA 3.0
2017-06-05T07:55:40.043Z
@TayfunPay Example: Given  $U=[6]$, $S_1=\{2,3,4\}$, $S_2=\{4,5\}$, $S_3=\{1,5\}$, $S_4=\{3,4,5\}$,..,$k=3$ first step $S_1=\{2,3,4\}$ second step $S_1\cap S_2=\{4\}$ third step $S_1\cap S_2 \cap S_4=\{4\}$.
GOLD
<cc.complexity-theory><ds.algorithms><graph-algorithms><logspace>
Restricted k-set cover is in NL or L
GOLD
# Restricted k-set cover is in NL or L

(Asked by: username_0 on 2017-06-01)

**Restricted** **$k$-set** **cover**:

**Input:** $(U,S\_1,S\_2,\cdots, S\_n, k)$, $U=[n]$ and $S\_i\subseteq U$ for all $1\leq i \leq n$.

**Output:** $\bigcap\_{i\in I}S\_i$ where $I=\{1,i\_1,i\_2\cdots,i\_k\},
i\_1=min(S\_1),i\_2=min(S\_1\cap S\_{i\_1}), \cdots, i\_k=min(S\_1\cap S\_{i\_2}\cap\cdots\cap S\_{i\_{k-1}})$

This problem is **Restricted** **$k$-set** **cover**
I want to know the above problem is in **L** or **NL**?

I trying to show this problem is in **NL**-complete. But I did not get any problem which is **NL**-complete connects to this problem.

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, logspace

> **Comments:**
> **username_1**: [Check this out.][1]      [1]: https://books.google.com/books?id=_qptCQAAQBAJ&pg=PA667&lpg=PA667&dq=%22restricted%20set%20cover%22&source=bl&ots=XbZuStphxm&sig=pm89fCeZrqxtVcJnItgeljKZPjw&hl=en&sa=X&ved=0ahUKEwjO47vWj57UAhVDSyYKHQYLBfQQ6AEIJzAA#v=onepage&q=%22restricted%20set%20cover%22&f=false  
> **username_0**: @TayfunPay their (given ref) definition of restricted $k$-set cover different from this definition. Even in their [original paper](http://cglab.ca/~morin/publications/fpt/covering-dcg.pdf) definition of restricted $k$-set cover no existence.  
> **username_1**: Can you explain yours with an example?  
> **username_2**: So it seems that when you're checking for membership in each $S_{i_j}$, you need to keep all $i_{p < j}$. For this reason, its not straightforward why it would be in $L$, let alone $NL$.. Cool problem though, it feels like one of these ones which would have the same parallel lower bound as sequential.  
> **username_0**: @TayfunPay Example: Given  $U=[6]$, $S_1=\{2,3,4\}$, $S_2=\{4,5\}$, $S_3=\{1,5\}$, $S_4=\{3,4,5\}$,..,$k=3$ first step $S_1=\{2,3,4\}$ second step $S_1\cap S_2=\{4\}$ third step $S_1\cap S_2 \cap S_4=\{4\}$.  

---

## 0 answers

