| Abstract: | We consider the problem of finding a subgraph of a given graph maximizing a given function evaluated at its degree sequence. While it is intractable already for convex functions, we show it is polynomial time solvable for convex multi-criteria objectives. We also consider a colored extension of the problem with separable objectives, which includes the notorious exact matching problem as a special case, and show that it is polynomial time solvable on graphs of bounded tree-depth for any vertex functions. |
