# P-complete problems on trees

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.

• Some motivation might help. – Suresh Venkat Nov 9 '11 at 16:41
• I would like to use such a problem in proving hardness of some problems on bounded tree width graphs. – Shiva Kintali Nov 9 '11 at 16:46
• – Chad Brewbaker Apr 25 '14 at 1:39

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?

• 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. – NisaiVloot Feb 20 '14 at 16:16
• Also, I have an idea for a third problem involving colored BSP trees, but I have to figure out the precise definition. Stay tuned... – NisaiVloot Feb 21 '14 at 9:52
• Your update in a separate answer to this answer should be a comment or an edit. Hence, I have deleted it. – Lev Reyzin Apr 24 '14 at 19:47
• 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'. – 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.

• Why is this a "third problem"? Is this an addition to another answer? – Lev Reyzin Apr 25 '14 at 1:46
• And why can't you combine it with your other answer ? – Suresh Venkat Apr 25 '14 at 2:57
• 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. – Super8 Apr 25 '14 at 3:31
• 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". – Suresh Venkat Apr 25 '14 at 13:17