On Computational Aspects of Cores of Ordered Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911292161261568 |
|---|---|
| author | Čertík, Michal Feldmann, Andreas Emil Nešetřil, Jaroslav Rzążewski, Paweł |
| author_facet | Čertík, Michal Feldmann, Andreas Emil Nešetřil, Jaroslav Rzążewski, Paweł |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23099 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Computational Aspects of Cores of Ordered Graphs Čertík, Michal Feldmann, Andreas Emil Nešetřil, Jaroslav Rzążewski, Paweł Computational Complexity Discrete Mathematics Combinatorics 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. |
| title | On Computational Aspects of Cores of Ordered Graphs |
| topic | Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2511.23099 |