论文标题
在程度序列优化上
On Degree Sequence Optimization
论文作者
论文摘要
我们考虑找到给定图的子图的问题，该图可以最大程度地利用以程度序列评估的给定函数。虽然问题已经很棘手，但我们表明它可以在多项式时间内解决凸多准则目标。接下来，我们考虑了可分离目标的问题，当所有顶点函数都是正方形时，这已经是NP-HARD。我们将可分离问题的彩色扩展视为一种特殊情况，其中包括臭名昭著的确切匹配问题，并证明它可以在任何顶点函数的有界树深度图上以多项式时间求解。我们提到了许多剩下的开放问题中的一些。
We consider the problem of finding a subgraph of a given graph which maximizes a given function evaluated at its degree sequence. While the problem is intractable already for convex functions, we show that it can be solved in polynomial time for convex multi-criteria objectives. We next consider the problem with separable objectives, which is NP-hard already when all vertex functions are the square. We consider a colored extension of the separable problem, which includes the notorious exact matching problem as a special case, and show that it can be solved in polynomial time on graphs of bounded tree-depth for any vertex functions. We mention some of the many remaining open problems.
