TR-2008-03

Deciding Soccer Scores and Partial Orientations of Graphs

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



Abstract

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:

@techreport{egres-08-03,
AUTHOR = {P{\'a}lvölgyi, Dömötör},
TITLE = {Deciding Soccer Scores and Partial Orientations of Graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2008},
NUMBER = {TR-2008-03}
}


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