Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
What do you mean by overridden? –  Noah Stein Mar 24 at 12:08
    
clarification on "overridden": * 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 (i.e. in these path that arrive to v - there is no node marked with N after the node marked with P until we arrive to v - including v). * 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 (i.e in this path to v there is no P after the N until we arrive to v - including v). –  user2660770 Mar 25 at 13:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.