Refining the complexity of the sports elimination problem

Katarína Cechlárová, Eva Potpinková, Ildikó SchlotterDiscret. Appl. Math 2016 · DOI · OpenReview

Abstract

The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This problem can be viewed as a graph labelling problem, where arcs receive labels that contribute to the score of both endpoints of the arc, and the aim is to label the arcs in a way that each vertex obtains a score not exceeding its capacity. We investigate the complexity of this problem in detail, using a multivariate approach to examine how various parameters of the input graph (such as the maximum degree, the feedback vertex/edge number, and different width parameters) influence the computational tractability. We obtain several efficient algorithms, as well as certain hardness results.
BibTeX
@article{cechlarova2016refining,
  author = {Katarína Cechlárová and Eva Potpinková and Ildikó Schlotter},
  title = {{Refining the complexity of the sports elimination problem}},
  journal = {Discret. Appl. Math.},
  year = {2016},
  doi = {10.1016/j.dam.2015.01.021},
}

Loading related content...

Figure