NP-Hardness: Finding the Best Subtree for Hierarchical Matching in Elasticsearch

Question

Given a graph G = (V, E) (a forest) stored in Elasticsearch and a set of requests R, where each request r in R can potentially match between 0 and V vertices in G, the task is to identify the "best" match for these requests. The goal is to mark the minimal subtrees within G that correspond to the requests. The solution should prioritize depth in the hierarchy over breadth, up to a specified ratio.

To achieve this, each request will require:

• A separate query to Elasticsearch, which, while computationally expensive, can be executed concurrently.
• A decision on whether the request aligns with an entire subtree or with a specific node.

This problem appears to be NP-Hard. Therefore, an Approximation Algorithm may be appropriate, as there is no strict requirement for an optimal solution.

Could you recommend a relevant algorithm to tackle this problem?

Answer 1

This is a naive heuristic, but worth a shot

Begin by considering the "root" request, treating it as the primary query. Attempt to identify a direct match for this request within the graph G=(V,E), without immediately addressing the subordinate requests.

Upon successfully matching the root request, proceed to address the subordinate requests. In this step, prioritize matches that align with vertices or subtrees that are descendants of the vertex matched by the root request.

This heuristic leverages a depth-first strategy, where the matching process first focuses on the primary request and then iteratively refines the solution by considering substructures.