From fafe39e65241f4bc041e35e6c82624e8b5a67d65 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 21 Oct 2022 16:37:24 +0200 Subject: Add LCA closure open question --- mgr.tex | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) 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} -- cgit v1.2.3