4

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path. This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover: Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to ...


4

(Sorry but not enough reputation otherwise this would be a comment.) Note that set difference is equivalent to set intersection with the complement i.e. $S_i\backslash S_j = S_i \cap \overline{S_j}$. Thus you could double the number of sets to $S_1, S_2, ...., S_k, \overline{S_1}, ..., \overline{S_k}$ and apply the set intersection pre-processing to the ...


2

Yes, let's require even less and say you're just interested in figuring out if the difference (similarly, intersection) is empty or not. It is trivial to have a quadratic-sized data structure with constant time query (by pre-processing everything) and also a linear-sized structure with linear query time (by just storing the sets trivially), and it's natural ...


2

I posed this question as a challenge to my students and I'm proud to report that they did not disappoint! Here's an argument based on ones developed by my students Kevin Tan and Max Arseneault, providing an intuition as to how the marking rule, applied to binomial trees, gives rise to the Fibonacci sequence. Our goal will be to find a lower bound on the ...


1

Your description of an example of your question #2 of having vertex weights and distributing the weight on some $v$ to its neighbours sounds reminiscent of the discharging method famously used in proofs towards the 4-colour theorem. That method, though, had weights assigned to vertices and to the faces of the (planar) graph. But I believe the discharging ...


1

Today you should probably use Tabulation hashing for Linear Probing. In The Power of Simple Tabulation Hashing by Mihai Pătrașcu and Mikkel Thorup, this is shown to have at least the same guarantees as 5 independent hashing. Later work shows that it gives you better concentration (worst case bounds) as well. Tabulation hashing is also a lot faster than even ...


Only top voted, non community-wiki answers of a minimum length are eligible