How to improve this algorithm for building a graphs closures
Since your nodes are double-linked (i.e. each has a list of all parents and children), creating the list of closures for all children of a certain node (especially the root node) seems like an overkill, especially if you're doing that whenever you start to filter. If you have a doubly linked graph, descendant and ancestor lists seem pretty cheap to get for each node, and for a large graph you will have to waste an awful lot of memory to keep them around.

If I am not mistaken, for each "chosen" node, you need to mark that node as safe, mark its children as safe, then traverse back to the root and mark all nodes you encounter as safe, and finally remove all non marked nodes. That should be much less work than you're doing now, if I didn't misunderstand the problem completely.

Some minor issues:


To merge two HashSets, it's much cheaper to use HashSet.UnionWith, than to create a new HastSet each time (like you're doing in your Filter method).
Btw, by looking at your code, it seems that Node.AnyDescendant should iterate through Children, not Parents.


I.e. wouldn't this work:

public static Node Filter(Node startNode, IEnumerable&lt;int&gt; includedNodes)
{
    var explicitlyIncludedNodes = startNode
        .Descendants()
        .Where(n =&gt; includedNodes.Contains(n.Id));

    var nodesToKeep = new HashSet&lt;int&gt;();
    foreach (var node in explicitlyIncludedNodes)
    {
        nodesToKeep.UnionWith(node.Ancestors().Select(n =&gt; n.Id));
        nodesToKeep.UnionWith(node.Descendants().Select(n =&gt; n.Id));
    }

    return BreadthFirstDeletion(startNode, nodesToKeep, includedNodes.ToArray());
}


Ancestors() should simply return all ancestors all the way to the root:

public IEnumerable&lt;Node&gt; Ancestors()
{
    var stack = new Stack&lt;Node&gt;();
    stack.Push(this);
    while (stack.Count != 0)
    {
        var current = stack.Pop();
        yield return current;

        foreach (var child in current.Parents)
            stack.Push(child);
    }
}


(Descendants the same way but for Children instead of Parents)