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.
Thank you for your comments.