MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
    
What do you mean by overridden? – Noah Stein Mar 24 '14 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 '14 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.