Deciding Soccer Scores and Partial Orientations of Graphs

Dömötör Pálvölgyi


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 undirected 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.

Bibtex entry:

AUTHOR = {P{\'a}lvölgyi, Dömötör},
TITLE = {Deciding Soccer Scores and Partial Orientations of Graphs},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-03}

Last modification: 13.3.2018. Please email your comments to Tamás Király!