P-complete problems on trees

Question

This question is related to one of my previous questions, NP-hard problems on trees.

I am looking for problems that are P-complete on trees.

Answer 1

A recent one, presented at ICALP is

Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221

You will find the paper both on arxiv and here.

Another example is Mostowski epimorphism (see P-completeness and efficient parallelization by Satoru Miyano, and the paper by Dahlhaus):

Dahlhaus E, Is SETL a suitable language for parallel programming - a theoretical approach, Computer science logic, 1st Workshop, CSL ’87, Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 329, 56-63, 1988)

Instance: a directed acyclic graph $D = (V, A)$ satisfying the axiom of extensionality and two vertices $x_1, x_2 \in V$

Problem: Decide whether $M_D(x_1) = M_D(x_2)$, where $M_D$ is the Mostowski epimorphism for $D$.

Answer 2

It depends a bit on what kind of problems you're looking at, but the path systems problem may be a candidate.

Given: A finite set of propositions $P$, a set $A \subseteq P$ of axioms, a set $R \subseteq P \times P \times P$ of inference rules and some target $p \in P$.

Question: Is $p$ provable from $A$ using $R$?

Here, every proposition in $A$ is provable from $A$ using $R$ and, if there's a rule $(p_1,p_2,p_3)$ in $R$ and $p_1$ and $p_2$ are provable from $A$ using $R$, then also $p_3$ is provable from $A$ using $R$.

The point is that the structure of such a proof is a tree.

A closely related problem is the language emptiness problem for a context-free grammar: Given a context-free grammar, does it have at least one derivation tree? (The reduction from path systems is almost immediate.) Therefore, language emptiness of context-free grammars is P-complete. Due to a very similar reason, the emptiness problem for tree automata is also P-complete.

A reference on path systems is: Stephen Cook: An Observation on Time-Space storage trade-off. JCSS, 1974.

Answer 3

I'd like to suggest some possible candidates for P-completeness:

• the Generalized Pebbling Game for trees (see "An Application of Generalized Tree Pebbling to Sparse Matrix Factorization" by J.W.H. Liu)
• The Agreement Supertree problem in phylogenetics (see "Fixed-Parameter Algorithms for Agreement Supertrees" by D. Fernandez-Baca et al).

The P-completeness is not clear to me though, a reduction from HornSAT seems possible but tricky; maybe the Target Set Selection problem would be a more natural starting point?

Answer 4

Here is the third problem I mentioned, called Quad Tree Recoloring. We are given:

• a matrix of colors $\Gamma = (\gamma_{i,j})$,
• a quad-tree $T$ whose leaves are labelled by elements of $\Gamma$,

and the goal is to recolor the minimum number of nodes of $T$ such that no two adjacent nodes of $T$ are labelled by colors adjacent in $\Gamma$.

Another possible cost function would be to count the surface of recolored nodes instead of their number. I conjecture that this problem is P-complete, but even membership in P is not immediate.