Unanswered Questions

23
votes
0answers
631 views

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})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
21
votes
0answers
360 views

Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

Let's assume the following definition of a red-black tree: It is a binary search tree. Each node is colored either red or black. The root is black. Two nodes connected by an edge cannot be red at ...
19
votes
0answers
186 views

Finding an st-path in a planar graph which is adjacent to the fewest number of faces

I am curious whether the following problems has been studied before, but wasn't able to find any papers about it: Given a planar graph G, and two vertices s and t, find an st-path $P$ which minimizes ...
19
votes
0answers
1k views

Is it NP-hard to fill up bins with minimum moves?

There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$. You start with $b_j$ balls of type $j$. Each ball of ...
19
votes
0answers
415 views

Subset sum problem with many divisibility conditions

Let $S$ be a set of natural numbers. We consider $S$ under the divisibility partial order, i.e. $s_1 \leq s_2 \iff s_1 \mid s_2$. Let $\qquad \displaystyle \alpha(S) = \max \{|V| \mid V\subseteq S, ...
19
votes
1answer
762 views

Is Logical Min-Cut NP-Complete?

Logical Min Cut (LMC) problem definition Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can ...
15
votes
0answers
290 views

Approximate minimum-weighted tree decomposition on complete graphs

Say I have a weighted undirected complete graph $G = (V, E)$. Each edge $e = (u, v, w)$ is assigned with a positive weight $w$. I want to calculate the minimum-weighted $(d, h)$-tree-decomposition. By ...
14
votes
0answers
21 views

Is there an efficient algorithm for this vertex cycle cover problem?

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as ...
14
votes
0answers
249 views

Solving divide & conquer reccurences if the split-ratio depends on $n$

Is there a general method to solve the recurrence of the form: $T(n) = T(n-n^c) + T(n^c) + f(n)$ for $c < 1$, or more generally $T(n) = T(n-g(n)) + T(r(n)) + f(n)$ where $g(n),r(n)$ are some ...
14
votes
1answer
301 views

Problems for which algorithms based on partition refinement run faster than in loglinear time

Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
13
votes
0answers
265 views

Graph problem known to be $NP$-complete only under Cook reduction

The theory of NP-completeness was initially built on Cook (polynomial-time Turing) reductions. Later, Karp introduced polynomial-time many-to-one reductions. A Cook reduction is more powerful than a ...
13
votes
1answer
413 views

Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
12
votes
0answers
95 views

Machines for context-free languages which gain no extra power from nondeterminism

When considering machine models of computation, the Chomsky hierarchy is normally characterised by (in order), finite automata, push-down automata, linear bound automata and Turing Machines. For the ...
12
votes
0answers
161 views

Is there an O(n log n) algorithm for 4D line simplification?

The Ramer-Douglas-Peucker algorithm for line simplification has worst-case $O(n^2)$ runtime. For suitably distributed random inputs, it has expected $O(n \log n)$ runtime complexity. In 2D, there are ...
12
votes
1answer
789 views

Is there a faster solution for the Google Code Jam Great Wall Problem

Consider the following Google Code Jam round 1C question: The Great Wall of China starts out as an infinite line, where the height at all locations is $0$. Some number of tribes $N$, $N \le 1000$, ...

15 30 50 per page