An ordered graph is a graph enhanced with a linear order on the vertex set. An ordered graph is a core if it does not have an order-preserving homomorphism to a proper subgraph. We say that $H$ is the core of $G$ if (i) $H$ is a core, (ii) $H$ is a subgraph of $G$, and (iii) $G$ admits an order-preserving homomorphism to $H$. We study complexity aspects of several problems related to the cores of ordered graphs. Interestingly, they exhibit a different behavior than their unordered counterparts. We show that the retraction problem, i.e., deciding whether a given graph admits an ordered-preserving homomorphism to its specific subgraph, can be solved in polynomial time. On the other hand, it is \NP-hard to decide whether a given ordered graph is a core. In fact, we show that it is even \NP-hard to distinguish graphs $G$ whose core is largest possible (i.e., if $G$ is a core) from those, whose core is the smallest possible, i.e., its size is equal to the ordered chromatic number of $G$. The problem is even \wone-hard with respect to the latter parameter.

翻译：有序图是在图的顶点集上赋予线性序的增强结构。若一个有序图不存在保持序的同态映射到其真子图，则称其为核心。若满足以下条件，则称 $H$ 为 $G$ 的核心：(i) $H$ 是核心，(ii) $H$ 是 $G$ 的子图，且 (iii) $G$ 存在保持序的同态映射到 $H$。本文研究了与有序图核心相关的若干问题的计算复杂性。有趣的是，这些问题展现出与其无序图版本不同的行为特征。我们证明，收缩问题（即判定给定图是否存在保持序的同态映射到其特定子图）可在多项式时间内求解。另一方面，判定给定有序图是否为核心是 \\NP 困难的。事实上，我们进一步证明，区分核心最大（即 $G$ 本身为核心）的图与核心最小（即核心大小等于 $G$ 的有序色数）的图甚至是 \\NP 困难的。针对后一参数，该问题甚至是 \\wone 困难的。