Add LCA closure open question

1 files changed, 16 insertions, 0 deletions

diff --git a/mgr.tex b/mgr.tex
index 8b1ea5a..8005fd9 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -1285,6 +1285,22 @@ With our algorithm we get, ``for free'', an
 answering on structures of bounded treewidth. Indeed, bounded treewidth
 structures are MSO interpretable in trees in linear time \cite{courcelle1992}.
 
+\section{LCA closure question answering}
+
+In Section \ref{computing-closure} we showed that the following question answering
+problem
+\queryproblem{LCA closure question answering}{%
+    a tree $T$.
+}{%
+    given a set of tree vertices $S$, compute the LCA closure of $S$.
+}
+has an \qptime{$O(|T|)$}{$|S| \log |S|$} solution. An open question is whether
+this is an optimal solution. If the question answering step's complexity could
+be reduced to $O(|S|)$, MSO query answering on structures of bounded treewidth
+would then be known to be in \lineardelaylin. Or is there a lower bound on
+computing LCA closures in this setting, for example, would it be possible to
+reduce comparison sorting to computing LCA closures?
+
 \printbibliography
 
 \end{document}