Consider the follow problem:Input: $G=(V,E)$, a weighted $k$-partite graph with $n$ vertices.Output: $U \subseteq V$, one vertex from each part, maximizing the total weight of the induced graph $G[U]$.For fixed $k$ we can solve the problem in time $O(n^k)$ using brute-force.Is there a faster algorithm?Does this problem have a standard name?
Find max weight induced graph in a multipartite graph with one vertex from each part
cc.complexity theory;ds.algorithms;graph theory;graph algorithms;parameterized complexity