<p>I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length <span class="math-container">$i$</span> <span class="math-container">$S_i$</span>, have a list <span class="math-container">$L$</span> of possible items to append, and a boolean function <span class="math-container">$f$</span>, and wish to create a set <span class="math-container">$S_{i+1} = \{ l+a| l \in S_i a \in L \land f(l+a)=1 \} $</span>. (<span class="math-container">$l+a$</span> represents appending the item <span class="math-container">$a$</span> to <span class="math-container">$l$</span>) Specificlaly, I'm curious when <span class="math-container">$f(l+a)$</span> depends on a small number of indices, <span class="math-container">$I$</span>, meaning <span class="math-container">$\forall l_1, l_2 \in S_i, l_1[k] = l_2[k] \forall k \in I \implies f(l_1+a) = f(l_2+a)$</span>. I think it's better explained through an example like graph coloring.</p>

<p>Say you have a graph <span class="math-container">$G$</span> that you want to color. One way to do this is to make a list of its vertices <span class="math-container">$L = v_1,v_2 \dots v_n$</span>, and keep track of set <span class="math-container">$S_i$</span> of valid ways to color the vertices <span class="math-container">$v_1, v_2 \dots v_i$</span>, and update it sequentially to get <span class="math-container">$S_{i+1}$</span> until you reach <span class="math-container">$n$</span>. If you had an oracle algorithm which could take a set <span class="math-container">$S$</span> of colorings and return the subset of <span class="math-container">$S$</span> of colorings <span class="math-container">$c$</span> such that <span class="math-container">$c(v_a) = k_1 \land c(v_b) = k_b \dots \land c(v_z) = k_z$</span> in polynomial time, then one could create an easy polynomial algorithm for any given <span class="math-container">$\Delta$</span> to determine if there exists a 3-coloring of any graph with maximal degree <span class="math-container">$\leq \Delta$</span>. Specifically, you'd need at most <span class="math-container">$k^{deg(v_{i+1})}$</span> queries to check the <span class="math-container">$k$</span>-colorings of <span class="math-container">$v_{i+1}$</span>'s neighbors that have been colored before it.</p>

<p>Thus, since 3-coloring is NP-Complete, it stands to reason that no such data structure allows for such a query to be easily done in general. And this is true even with the information about which queries will be made, as it is trivial to get this information in the case of coloring. Yet, at the same time, there seems like a better way to do this than brute force, going through each list one by one. </p>

<p>For example, say we only made queries about the last <span class="math-container">$x$</span> items of our lists, <span class="math-container">$l \in S_i$</span>, with each item having at most <span class="math-container">$y$</span> possible values. Then, we can make rooted tree, where the edges from the root represent the possible values of <span class="math-container">$l[-1]$</span>, and the children represent the possible values of <span class="math-container">$l[-2]$</span> given the path to it, et cetera. Basically, to create the valid lists of length <span class="math-container">$i+1$</span>, for each of the possible values we could append, we make a copy of this tree, prune according to which paths are compatible with this.</p>

<p>Is there a name for this kind of query? If we know <span class="math-container">$I_i$</span>, the list of indices which matter at step <span class="math-container">$i$</span>, can do queries with faster complexity than brute force (<span class="math-container">$O(|S|)$</span>)? What about the case when <span class="math-container">$|I_i|$</span> is bounded, even by one?</p>

CC BY-SA 4.0
2019-08-29T03:13:37.557Z
What type do $l,a$ have?  What operation does $l+a$ represent?  What operations do you want the data structure to support?
D.W.
CC BY-SA 4.0
2019-08-29T03:34:02.707Z
$l$ is a list, all lists in $S_i$ have length $i$. $a$ is an item we wish to append. $l+a$ is $a$ appended to $l$. the main operations are pruning, appending and unions. pruning means given indices $i_a, \dots i_z$ and sets of values $(k_{a,1} \dots k_{a,m_a}), \dots (k_{z,1}, \dots k_{z,m_z})$, we remove all lists in $S$ if $\exists x \in [a,z] \exists y \in [1,m_x] | l[i_x] = k_{x,y}$. In paragraph 4 I note that if we only prune the last $x$ indices, and have at most $y$ different items possible for each index, then we can do this polynomially with prefix trees. but thats exponential in $x$.
Zach Hunter
CC BY-SA 4.0
2019-08-29T04:23:52.913Z
I suggest you edit the question to state explicitly the operations and define what operation + represents.
D.W.
<ds.data-structures><counting-complexity>
Updating set of lists dependent upon a few indices
Zach Hunter
# Updating set of lists dependent upon a few indices

(Asked by: username_0 on 2019-08-28)

I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S\_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to create a set $S\_{i+1} = \{ l+a| l \in S\_i a \in L \land f(l+a)=1 \} $. ($l+a$ represents appending the item $a$ to $l$) Specificlaly, I'm curious when $f(l+a)$ depends on a small number of indices, $I$, meaning $\forall l\_1, l\_2 \in S\_i, l\_1[k] = l\_2[k] \forall k \in I \implies f(l\_1+a) = f(l\_2+a)$. I think it's better explained through an example like graph coloring.

Say you have a graph $G$ that you want to color. One way to do this is to make a list of its vertices $L = v\_1,v\_2 \dots v\_n$, and keep track of set $S\_i$ of valid ways to color the vertices $v\_1, v\_2 \dots v\_i$, and update it sequentially to get $S\_{i+1}$ until you reach $n$. If you had an oracle algorithm which could take a set $S$ of colorings and return the subset of $S$ of colorings $c$ such that $c(v\_a) = k\_1 \land c(v\_b) = k\_b \dots \land c(v\_z) = k\_z$ in polynomial time, then one could create an easy polynomial algorithm for any given $\Delta$ to determine if there exists a 3-coloring of any graph with maximal degree $\leq \Delta$. Specifically, you'd need at most $k^{deg(v\_{i+1})}$ queries to check the $k$-colorings of $v\_{i+1}$'s neighbors that have been colored before it.

Thus, since 3-coloring is NP-Complete, it stands to reason that no such data structure allows for such a query to be easily done in general. And this is true even with the information about which queries will be made, as it is trivial to get this information in the case of coloring. Yet, at the same time, there seems like a better way to do this than brute force, going through each list one by one.

For example, say we only made queries about the last $x$ items of our lists, $l \in S\_i$, with each item having at most $y$ possible values. Then, we can make rooted tree, where the edges from the root represent the possible values of $l[-1]$, and the children represent the possible values of $l[-2]$ given the path to it, et cetera. Basically, to create the valid lists of length $i+1$, for each of the possible values we could append, we make a copy of this tree, prune according to which paths are compatible with this.

Is there a name for this kind of query? If we know $I\_i$, the list of indices which matter at step $i$, can do queries with faster complexity than brute force ($O(|S|)$)? What about the case when $|I\_i|$ is bounded, even by one?

**Tags:** ds.data-structures, counting-complexity
> **Comments:**
> **username_1**: What type do $l,a$ have?  What operation does $l+a$ represent?  What operations do you want the data structure to support?  
> **username_0**: $l$ is a list, all lists in $S_i$ have length $i$. $a$ is an item we wish to append. $l+a$ is $a$ appended to $l$. the main operations are pruning, appending and unions. pruning means given indices $i_a, \dots i_z$ and sets of values $(k_{a,1} \dots k_{a,m_a}), \dots (k_{z,1}, \dots k_{z,m_z})$, we remove all lists in $S$ if $\exists x \in [a,z] \exists y \in [1,m_x] | l[i_x] = k_{x,y}$. In paragraph 4 I note that if we only prune the last $x$ indices, and have at most $y$ different items possible for each index, then we can do this polynomially with prefix trees. but thats exponential in $x$.  
> **username_1**: I suggest you edit the question to state explicitly the operations and define what operation + represents.  

---

## 0 answers

