A constrained topological sort?

Solution 1:

Some cases of your problem are solvable by greedy approach. For example $r \ge n$ and $\{\,a_1, a_2, \ldots, a_n\,\} = \{\,1, 2, \ldots, n\,\}$. In this case penalty function tells that the last vertex in our ordering should have the smallest possible value and no matter how all other vertices are placed. Topological order says that it also should have no outgoing arcs. So we should place there a vertex with smallest value among all vertices without outgoing arcs and solve a subproblem. Using heap we can get $O(n \log n + m)$ time for $n$ vertices and $m$ arcs.

In general case the problem seems to be NP-hard. However I failed to prove this fact.

Prove the determinant of this matrix

How does one cut onions in a mathematically efficient way?

Geometric interpretation of the determinant of a complex matrix

Prove that $\sqrt{a^2+3b^2}+\sqrt{b^2+3c^2}+\sqrt{c^2+3a^2}\geq6$ if $(a+b+c)^2(a^2+b^2+c^2)=27$

If $\left(1^a+2^a+\cdots+n^{a}\right)^b=1^c+2^c+\cdots+n^c$ for some $n$, then $(a,b,c)=(1,2,3)$?

What is the correct way to self learn from a textbook?

When is a fibration a fiber bundle?

Find $a,b,c,d,e$ such that $\frac{s}a+1,\frac{s}b+1,\frac{s}c+1,\frac{s}d+1,\frac{s}e+1$ are all perfect squares $ (s=abcde)$

Prove that $\frac{a^n-1}{b^n-1}$ and $\frac{a^{n+1}-1}{b^{n+1}-1}$ can't both be prime.

Prove that the map $\phi:S^3\times S^3\to{\bf GL}(4,\Bbb R)$ defined via quaternions as$\phi(p,q)(v)=pvq^{-1}$ has image ${\bf SO}(4)$

Is there a closed form for this sum?