is there a polynomial solution for the below problem? is it similar to a known problem in graph theory?
Given a directed graph G with cycles such that:
• G has a start node s with a path to every other node v.
• All nodes have weights
Then an assignment to G is to label some of its nodes by P and some of its nodes by N. We define the following:
• Let Pk =v1->v2->… -> vk be a sub-path of size k possibly with cycles.
• A node v ∈ G is under the influence of P if all the paths from s to v contain a node marked with P that is not overridden by a N node.
• A node v ∈ G is under the influence of N if there is some path from s to v that contains a node marked with N that is not overridden by a P node.
• An assignments to G is K-T legal if all paths Pk =v1->… ->vk of length k≤K with total weights ≥T, have their first node v1 under the influence of P and the rest of Pk nodes v2, ..,vk are not labeled by N.
• The profit of a legal K-T assignment is the total length of paths with length k>K and total weights < T that are under the influence of N.
Given G as above we seek to find K-T assignment with maximal profit