0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ What type do $l,a$ have? What operation does $l+a$ represent? What operations do you want the data structure to support? $\endgroup$
    – D.W.
    Aug 29, 2019 at 3:13
  • $\begingroup$ $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$. $\endgroup$
    – Zach Hunter
    Aug 29, 2019 at 3:34
  • $\begingroup$ I suggest you edit the question to state explicitly the operations and define what operation + represents. $\endgroup$
    – D.W.
    Aug 29, 2019 at 4:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy