# Two Decision Problems About Graphs --- Original Results?

I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell?

I don't have easy access to any standard texts that would help me out here. Nor indeed do I work in the field (but it would still be advantageous as well as personally satisfying if I could get a note in some journal or other). Anyway, enough prolog, on with the results.

Consider these two closely related problems:

PROBLEM 1: A complete digraph has its edges labeled with numbers. The "average score" of a circuit (not necessarily a cycle) in the graph is defined as the sum of the numbers along the edges traversed divided by the number of edges in the circuit. Is there a non-self-intersecting circuit having an average score greater than a given number?

PROBLEM 2: The same problem, except with the additional constraint that the circuit must pass through a given vertex of the graph.

Problem 1 can be solved in polynomial time. Problem 2 is NP-complete.

• What is a circuit? Commented Sep 29, 2011 at 23:03
• @RaduGRIGore: a closed walk. Commented Sep 30, 2011 at 0:28
• IMHO, this is not on-topic (checking if a theorem that is proven by a non-TCS researcher is already known). It might be suitable for Math.SE. Commented Sep 30, 2011 at 11:45
• In general it seems to me (no expert) that NP-completeness results are a dime a dozen -- basically anyone in CS can make up a problem and prove it NP complete. So proving some problem NP complete is only interesting if the problem is interesting for some other reason.
– Max
Commented Oct 6, 2011 at 17:54

Problem 1 is an exercise in CLRS (2nd ed., page 617).

It sounds as though your first problem is the computation of the maximum cycle mean. I am no expert, but I know the problem is well studied. One paper on the subject that is not behind a paywall can be found here.