# Tag Info

20

The second-smallest spanning tree differs from the minimum spanning tree by a single edge swap. That is, to get the second-smallest tree, you need to add one edge that's not already in the minimum spanning tree, and then remove the heaviest edge on the cycle that the added edge forms. If you already have the minimum spanning tree, this can all be done in ...

9

According to https://www.cse.ust.hk/~golin/pubs/ANALCO_05.pdf there is no closed-form formula known. According to http://arxiv.org/pdf/cond-mat/0004341v1.pdf the number is asymptotic (for $n$ and $m$ both large) to $$\exp (z_{\mathrm{sq}}mn)$$ where $$z_{\mathrm{sq}}=\frac{4}{\pi}\sum_{i=0}^\infty\frac{(-1)^i}{(2i+1)^2}\approx 1.16624$$ but I'm not sure ...

8

Empire colouring is NP-hard for trees. Let $r$ and $s$ be fixed positive integers, and let $G$ be a graph whose vertex set is partitioned into blocks (or empires) each containing exactly $r$ vertices. The $(s, r)$-colouring problem $s$-$\text{COL}_r$ asks for a colouring of the vertices of the graph $G$ that uses at most $s$ colours, never assigns the ...

8

Given a tree $T$, a partition of $V(T)$ in $k$ levels $\phi: V(T)\to \{1,\ldots, k\}$ (i.e., edges of $T$ connect vertices of neighbouring levels $i$ and $i+1$), and an integer $K$. Can you permute the vertices inside the levels such that the crossing number is at most $K$? This problem is NP-complete, proved by Martin Harrigan and Patrick Healy, $k$-Level ...

7

A flow in a network is confluent if it uses at most one outgoing arc at each node. NP-hardness of determining a maximum confluent flow in a tree (of diameter 4, with multiple sinks allowed) is proved in: D. Dressler and M. Strehler, Capacitated Confluent Flows: Complexity and Algorithms, LNCS 6078 (2010) 347-358.

7

The Travelling Repairman Problem (TRP) is known to be NP-hard on weighted trees. In this problem, which is also sometimes called the Minimum Latency Problem, the goal is to find a tour that visits all the vertices of a graph while minimizing the average latency. The latency of a vertex $u$ is the cost of the tour from the origin until the tour visits $u$. ...

7

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 element is optimal. See "Hash, displace, and compress" "Improved Bounds For Covering Complete Uniform Hypergraphs" Data Structures and Algorithms , Vol. 1: ...

7

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. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree). The same paper states that it ...

6

[Steiner tree] remains NP-complete if all edge weights are equal, even if $G$ is a bipartite graph having no edges joining two vertices in $C$ or two vertices in $V-C$. — Garey and Johnson, Computers and Intractability, Freeman, 1979. Citation is to private communication with E. R. Berlekamp.

6

A harmonious coloring of a simple graph is a proper vertex coloring such that each pair of colors appears together on at most one edge. The Harmonious Chromatic Number of a graph is least number of colors in a harmonious coloring of the graph. This problem of finding Harmonious Chromatic Number was shown to be NP-complete on trees by Edwards and McDiarmid. ...

6

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 $t$. This problem is often known as "$k$ Most Vital Edges (for MST)", simply $k$-MVE (or sometimes $k$-MVE-MST to distinguish from other variations), as cited ...

5

First, after each stage throw away any isolated vertices. With these vertices removed (even when the graph is disconnected) the number of vertices in the next stage will be at most twice the number of edges. Next, use the fact that (with isolated vertices removed, in each stage after the first) $|V|\le 2|E|$ to simplify the time bound in each stage (after ...

5

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. (In case we have to start with the empty tree, just insert $[n]$ in any order.) A result of Cleary [*1] (see also Lucas [*2]) shows that you can get from $... 4 The problem is solved in the paper P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976. It considers an even more general problem using dynamic programming. 4 Could not add a comment due to lack of reputation. As commented by David Eppstein you can find the proof of the fact that the second-smallest spanning tree differs from the minimum spanning tree by a single edge swap in the article "A combinatorial ranking problem", Burns and Haff. Basically, in the article an algorithm is presented for finding an$...

4

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$ is uniform on $[0,1]$, Frieze showed that $\lim_{n \to \infty} \mathbb{E}[L_n(\mu)] = \sum_{k\ge1}{\frac{1}{k^3}} = \zeta(3)$. Steele showed that for a $\mu$ ...

4

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 more expensive than 1.79 bits per key!

3

This problem is known as Decremental Connectivity. In general, decremental connectivity is where you need to support the operations: Connected($u$,$v$) : Check whether vertex $u$ is connected to vertex $v$ Delete($e$): Remove an edge $e$ Given $n$ queries of the first kind and $m$ queries of the second, Even and Shiloach [1] gave an $O(n\log{n} + m)$ ...

3

I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child. By induction you can prove ...

3

Let me give a side answer to your question. Consider the variant where you only care about edge-minimal spanning trees: for 2 terminals $s$ and $t$, the problem is equivalent to counting simple $s,t$-paths, which is $\# P$-complete; also, the parameterized version where you ask for paths of length $k$ is $\# W[1]$-hard. If you care about arbitrary $T$-...

3

Actually, the Damerau–Levenshtein distance is a metric. (See, for example, §11.1 of Encyclopedia of Distances, by Deza & Deza, Springer, 2009.) That is, it does obey the triangle inequality. This can be seen quite easily if you view every possible string as a node, with the edit operations and transpositions between them as edges. The Damerau–Levenshtein ...

3

Although not specifically aimed at (rooted) trees, I think the G-trie data structure might perform quite well in your setting. It is an adapation of the trie (for searching sets of strings) to graphs.

3

A graph $G(V, E)$ is 2-splittable if it is possible to partition its edge set into two subsets such that the induced subgraphs are isomorphic. Deciding whether a given graph is 2-splittable is $NP$-complete even if input is restricted to trees. Formally, the problem is: PARTITIONED GRAPH ISOMORPHISM INSTANCE: A tree $T = (V,E)$ QUESTION: Is there a ...

3

For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form $(i,j)$ with $i\in\{0,1\}$ and $i\leq j$. Being at level $(i,j)$ means that there is a parity automaton using parities from $i$ to $j$ recognizing the language. For more on parity condition, see here: https://en.wikipedia.org/...

3

I think the easiest way of enforcing tree shape is the set of conditions $q_0$ is not in the image of $\delta$, $\delta$ is injective, and $M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable. Then we can prove (by induction) that for any state $q$ there is a unique path from $q_0$ to $q$.

3

I think that the problem is not hard, because if I understood the problem statement correctly, it can be solved in $O(|V|^2)$ time as follows: We have two $0$-$1$-labeled rooted perfect full binary trees $(A, x)$ and $(B, y)$ with $2^k-1$ nodes. We compute the minimum number of mismatches in any isomorphism between the trees denoted by $F(A, B)$ recursively ...

3

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 infinite sequence of terms. Because $R$ is a WQO, there are $i, j$ with $i<j$ such that $t_i\ R\ t_j$. But this implies $t_i\ S\ t_j$, so $S$ is a WQO as well. ...

3

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 input is a star graph, then you need to know the orientation of every one of the $n-1$ edges). [1] Holm, Jacob, Eva Rotenberg, and Mikkel Thorup. "Planar ...

2

A zipper is in general a pair of things: it's a structure-with-a-hole, a focus, representing where in the structure you are, together with a path, recording how you got to that focus. (This path is LYAH's trail of breadcrumbs.) The path is how you actually apply changes to the structure: "go down, go left, increment the value". By repeatedly applying "go up"...

2

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 techniques from the paper which derives the $\Theta(\sqrt{n})$ asymptotics to the run trees of the regular language. Notice that a tree is accepted if there exists a run ...

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