Deciding Soccer Scores and Partial Orientations of Graphs
Dömötör Pálvölgyi · 2009
We show that deciding if a simple graph has a partial orientation of its edges such that all vertices have a prescribed in-, out- and undi-rected degree, is NP-complete. We prove a related question, that if we know that in a soccer-tournament who played who so far, but we do not know the outcomes, then deciding whether a score vector is legal or not, is NP-complete. 1