Is this tree minimization problem NP-complete?

Question

I'm totally new to complexity theory, hence don't know much about how reductions work. So, I'm not sure how hard the following problem is. Please let me know what kind of problems I should look at to attempt for a reduction to my problem (if it is NP-hard or complete). Even reduction from that problem to my problem (yielding this is NP-hard) would be a good result to have.

The problem is the following. Suppose, we have the set of all possible 'single rooted' trees with $n$ nodes, denoted by ${\cal T}$. The set of nodes is denoted by $N$. Each node has some intrinsic values $\gamma_i$ (these are given beforehand). The function $\mu : 2^N \to \mathbb{R}$ maps the children of each node to real numbers, and this function is also given beforehand. Another function $f: {\cal T} \to \mathbb{R}$ maps the subtree of a given node to reals. Now the problem is,

$$ \min_{T \in {\cal T}} \sum_{i \in N} f(T_i) \mu (C_{p(i)}) (\gamma_{p(i)} - \gamma_i). $$

Where $T_i$ is the subtree rooted at $i$, $p(i)$ is the unique parent of $i$, $C_{p(i)}$ is the children set of $p(i)$. Given a tree $T$, both $f$ and $\mu$ are computable in linear time. The problem basically is to find the right connection of nodes over a tree.

Thanks in advance.

%%% Editing after getting the answer from Yuval %%%

Maybe I was unclear. For single rooted trees with $n$ nodes, one can have $(n-1)!$ possible trees (this can be enumerated using the incidence matrix of the tree and considering the placements of 1 in the upper triangular part), and in each of those trees, there are $n!$ ways to place the nodes (remember $\gamma_i$s are node identity specific). And so, in each of the $n! \times (n-1)!$ possible configurations, you'll get a value for the sum. The problem is to find the minimum over such a huge space. My question is: do there exist efficient algorithms to compute this min? Or, is the problem hard, i.e., no efficient algorithm exists?

Answer 1

Your problem is ill-defined. Since the functions $f\colon \mathcal{T} \rightarrow \mathbb{Q}$ and $\mu\colon 2^N \rightarrow \mathbb{Q}$ (rather than real-valued) have a very long description, you can go over all possible trees $T \in \mathcal{T}$ in polynomial time.

To make the question more meaningful you might want the algorithm to have oracle access to $f$ and $\mu$, and then instead of NP-completeness you might want to prove a lower bound on the number of evaluations of $f$ and $\mu$.

Another possibility is that $f$ and $\mu$ have some structure and so can be specified succinctly. If this is the case, then you need to refine the problem reflecting that feature.

A similar problem occurs in submodular optimization. Suppose we want to maximize a monotone submodular function over a matroid constraint. There are several randomized polynomial time algorithms giving a $1-1/e$ approximation. There is a lower bound by Vondrák showing that in the (so-called) value oracle model, any better approximation requires evaluating the function at exponentially many places (this lower bound is information-theoretic rather than complexity-theoretic). Feige proved that a special case of the problem, maximum coverage, is NP-hard to approximate better than this ratio. Finally, Vondrák and Dobzinski show how to lift the value oracle result to a complexity result in the succinct representation model, assuming RP$\neq$NP (rather than P$\neq$NP as in Feige's result); the technique (whose main ingredient is list-decoding) also gives results that Feige's can't.