7 votes
Accepted

Complexity of reachability in directed rooted forests

The problem is L-complete. It’s easier to think about it when the edges are written backwards. That is, I will consider the problem formulated as follows: given a directed acyclic graph such that ...
Emil Jeřábek's user avatar
7 votes
Accepted

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

2.09 bits per element is practically achievable. See http://cmph.sourceforge.net/: "[Compress, Hash, Displace] can generate MPHFs that can be stored in approximately 2.07 bits per key." 1.44 bits per ...
jbapple's user avatar
  • 11.2k
7 votes
Accepted

How fast can we find and disconnect roots in a forest?

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], thus overcoming the lower bound for generic version of the problem. ...
Dmitri Urbanowicz's user avatar
6 votes
Accepted

Complexity of "destroying" the graph's minimum spanning tree weight

EDIT As noted in comments below, I originally read the question incorrectly. I thought the goal was to determine if removing $k$ edges could increase the MST weight of $G$ above some given threshold $...
mhum's user avatar
  • 3,382
5 votes
Accepted

For a given binary-search tree obtain an isomorphic splay tree

It can be done with a linear number of operations. Suppose you start with an arbitrary given tree $T_0$ over keys $[n]$ and want to reach an arbitrary given $T$ over keys $[n]$ using splay operations....
László Kozma's user avatar
5 votes

Notion of "quotient" or "inverse" for recognizable tree languages?

The Myhill-Nerode theorem characterizes regular/recognizable languages as those that have finitely many "quotients", and it works for trees — more precisely, a tree language is regular iff ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
4 votes
Accepted

If I naively generalize the homeomorphic embedding relation for labeled finite trees in this way, do I still have a wqo?

Here's a nice property of WQOs: If $R$ is a WQO on terms, and $S$ is another transitive relation such that $$ R\ \subseteq\ S$$ Then $S$ is a WQO Proof: Let $t_1,\ldots, t_n,\ldots$ be an ...
cody's user avatar
  • 13.9k
4 votes

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

1.56 bits per key is now possible using "RecSplit: Minimal Perfect Hashing via Recursive Splitting" by Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. It is quite expensive: 1,700 times ...
jbapple's user avatar
  • 11.2k
4 votes

Minimum Spanning tree on a complete "random" graph

Let's consider a general model in which $L_n(\mu)$ is the (random) length of an MST on $K_n$, where the weight of each edge is sampled independently from a probability distribution $\mu$. When $\mu$ ...
Sasho Nikolov's user avatar
4 votes
Accepted

O(n)-space, polylog-time subtree sums in incremental forests?

It turns out this is possible with $O(n \log n)$ preprocessing time, polylog ($O(\log^3 n)$) query time and linear space: Convert the forest into binary trees of logarithmic height. For each node, ...
Dmytro Taranovsky's user avatar
3 votes
Accepted

Reachability Query for Tree

Follow-up work by Holm, Rotenberg and Thorup [1] showed that there exists a reachability oracle for planar graphs of size $O(n)$ and query time $O(1)$. This is optimal also for trees (e.g., if the ...
smapers's user avatar
  • 849
2 votes
Accepted

Complexity of finding a path visiting all leaves on a tree while respecting a distance bound

As the comments have suggested, you are looking for a Ham Path through a set nodes in the $k$-leaf power graph of this tree. That is, given your tree $T$ and a distance $k$, form a graph $G$ where $V(...
JimN's user avatar
  • 1,316
2 votes
Accepted

Spanning Tree that Preserves the Number of Branch Vertices

No, not even close. Lemma 1. For any $n\ge 6$, all $n$ vertices in the complete bipartite graph $K_{3,n-3}$ are branch vertices, but each spanning tree of the graph has at most 4 branch vertices. ...
Neal Young's user avatar
  • 10.6k
2 votes

O(n)-space, polylog-time subtree sums in incremental forests?

Thanks to Dmytro Taranovsky for the thorough answer. Here's my attempt to rephrase his answer in my own words. Without loss of generality, assume that $G$ consists of a single tree. First, we reduce ...
Mathias Rav's user avatar
2 votes

Is the center of a BFS tree a good approximation of the graphs center?

In the worst case, this algorithm gives a 2-approximation (the trivial upper bound). Take a cycle on some $n=4m$ vertices, vertex set $v_0,\ldots,v_{n-1}$, with one chord between $v_0$ and $v_{2m}$. ...
Highheath's user avatar
  • 211
2 votes
Accepted

Binary Trees for Nearest Neighbor Search

This essentially can be derived from a compressed quadtree representing approximate Voronoi diagrams. If you want the decision tree to be balanced you have to use a finger tree on the compressed ...
Sariel Har-Peled's user avatar
2 votes

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

I believe that the answer is as you suggest that no other asymptotics than $\Theta(1)$, $\Theta(\sqrt{n})$ and $\Theta(n)$ are possible. A promising route to prove this could be to apply the ...
Martin Hofmann's user avatar
2 votes

NP-hard problems on trees

k-Balanced Partition Problem on graphs, in which one has to partition the $n$ vertices into $k$ connected components of size at most $\lceil\frac{n}{k}\rceil$ each and at the same time minimize the ...
user1105's user avatar
  • 181
2 votes

Algorithm for computing unordered tree edit distance

A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly ...
SX.'s user avatar
  • 21
2 votes

Place of tree-adjoining grammars in the hierarchy of tree grammars

Actually I've found the answer. Here is quote from unpublished work (lecture notes?) of M. Kanazawa: The class of tree languages of tree-adjoining grammars is included in the class of tree ...
Andrey Lebedev's user avatar
2 votes
Accepted

What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?

The paper "Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth" (Elberfeld, Jacobi, Tantau) gives a nice balanced tree decomposition based on tree contraction in $TC^0$: ...
Danny's user avatar
  • 500
2 votes

What are "unranked trees"?

You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.
user53151's user avatar
1 vote
Accepted

Example of context-free tree language which can not be generated by monadic CFTG

Based on the comment of Michael Wehar, I've found this grammar to be that one which doesn't have an equivalent MCFTG: $S\rightarrow T(a,a)$ $T(x_1,x_2)\rightarrow T(b(x_1,x_2),c(x_1,x_2))$ $T(x_1,...
Andrey Lebedev's user avatar
1 vote

How to continue this algorithm?

A conceptually far simpler algorithm is to try all the options. Cut the rectangle into $g=gcd(w,\ell)$ squares. There are finitely many ways to portion these squares into non-overlapping blocks that ...
Stella Biderman's user avatar
1 vote
Accepted

Regarding proper form of production rules of Context-free tree grammars

After a couple of hours of thinking I found at least proper form of grammar. Thanks to @Sylvain's commentary and link to Fisher's paper, which given me a clue. Proper context-free tree grammar, which ...
Andrey Lebedev's user avatar
1 vote

Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

Your problem is in $P$. In fact, it can be solved in $O(n^2)$ time. Given a tree, you can find a label (a binary string) that is a canonical form for the tree (i.e., all isomorphic trees will share ...
D.W.'s user avatar
  • 12.1k
1 vote

Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New ...
Chad Brewbaker's user avatar
1 vote
Accepted

A non-trivial combinatorial optimization

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$. Proof sketch. Given ...
Neal Young's user avatar
  • 10.6k

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