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.


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$.


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 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?

  • $\begingroup$ On a related note, I think that the P-completeness of the second problem follows from "Resolving Rooted Triplet Inconsistency by Dissolving Multigraphs" by Chester et al. I'm not sure about the first one though. $\endgroup$ – NisaiVloot Feb 20 '14 at 16:16
  • $\begingroup$ Also, I have an idea for a third problem involving colored BSP trees, but I have to figure out the precise definition. Stay tuned... $\endgroup$ – NisaiVloot Feb 21 '14 at 9:52
  • $\begingroup$ Your update in a separate answer to this answer should be a comment or an edit. Hence, I have deleted it. $\endgroup$ – Lev Reyzin Apr 24 '14 at 19:47
  • $\begingroup$ I posted a separate answer to have it appear in the question stream, so let me repeat: the first problem 'Generalized Pebbling Game for trees' is probably NOT $\sf{P}$-complete as it seems solvable in $O(\log^2 n)$ space, at least in its current definition. Also, for the second problem it's a matter of interpretation whether it answers the question or not -- technically it involves a 'tree profile' rather than a 'tree'. $\endgroup$ – Super8 Apr 24 '14 at 22:07

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.

  • $\begingroup$ Why is this a "third problem"? Is this an addition to another answer? $\endgroup$ – Lev Reyzin Apr 25 '14 at 1:46
  • $\begingroup$ And why can't you combine it with your other answer ? $\endgroup$ – Suresh Venkat Apr 25 '14 at 2:57
  • $\begingroup$ Yes, this was an addition to the answer above; given the recent update this should be considered as a 'second problem' on my side. This problem was just a 'guesstimate' based on practical considerations, I'm still unsure about the membership in P; maybe considering alternative topologies such as hexagonal tilings could change the complexity? I'll keep looking for other candidates and I'll merge the answers eventually - assuming that I can access to the old 'Super8' profiles created 2 months ago. $\endgroup$ – Super8 Apr 25 '14 at 3:31
  • 2
    $\begingroup$ Using multiple profiles this way creates clutter and more work for mods. This is a shared resource, and it's upto all of us to keep things "tidy". $\endgroup$ – Suresh Venkat Apr 25 '14 at 13:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.