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.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
A recent one, presented at ICALP is
Markus Lohrey, Christian Mathissen: Isomorphism of Regular Trees and Words. ICALP (2) 2011: 210-221
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$.
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.
I'd like to suggest some possible candidates for P-completeness:
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?
Here is the third problem I mentioned, called Quad Tree Recoloring. We are given:
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.