论文标题
无环的本地锦标赛导向完成的障碍
Obstructions for acyclic local tournament orientation completions
论文作者
论文摘要
固定类别的图形类别的方向完成问题询问是否可以将给定的部分定向的图完成到类中的方向图。最近已经研究了几类方向图的方向完成问题，从而产生多项式时间解决方案和NP完整性结果。本地比赛是结构良好的定向图表，它们概括了锦标赛及其基础图与适当的圆形ARC图密切相关。正确的间隔图是可以将其定向为无环的本地锦标赛的图形。已经证明，当地比赛和无环的本地比赛的方向完成问题都是可以解决的多项式时间。在本文中，我们确定了无环的本地锦标赛导向完成的障碍。从某种意义上说，这些是最小的部分面向图表，无法完成针对无环的本地锦标赛。我们对障碍物的描述意味着它们可以在多项式时间内得到识别。在同伴论文中，我们将确定当地锦标赛取向完成的所有障碍。
The orientation completion problem for a fixed class of oriented graphs asks whether a given partially oriented graph can be completed to an oriented graph in the class. Orientation completion problems have been studied recently for several classes of oriented graphs, yielding both polynomial time solutions and NP-completeness results. Local tournaments are a well-structured class of oriented graphs that generalize tournaments and their underlying graphs are intimately related to proper circular-arc graphs. Proper interval graphs are precisely those which can be oriented as acyclic local tournaments. It has been proved that the orientation completion problems for local tournaments and acyclic local tournaments are both polynomial time solvable. In this paper we identify the obstructions for acyclic local tournament orientation completions. These are in a sense minimal partially oriented graphs that cannot be completed to acyclic local tournaments. Our description of the obstructions imply that they can be recognized in polynomial time. In a companion paper we will determine all obstructions for local tournament orientation completions.
