Complexity Aspects of Homomorphisms 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_ | 1866911292128755712 |
|---|---|
| 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 | We examine ordered graphs, defined as graphs with linearly ordered vertices, from the perspective of homomorphisms (and colorings) and their complexities. We demonstrate the corresponding computational and parameterized complexities, along with algorithms associated with related problems. These questions are interesting, and we show that numerous problems lead to various complexities. The reduction from homomorphisms of unordered structures to homomorphisms of ordered graphs is proved, achieved with the use of ordered bipartite graphs. We then determine the NP-completeness of the problem of finding ordered homomorphisms of ordered graphs and the XP and W[1]-hard nature of this problem parameterized by the number of vertices of the image ordered graph. Classes of ordered graphs for which this problem can be solved in polynomial time are also presented. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23078 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Complexity Aspects of Homomorphisms of Ordered Graphs Čertík, Michal Feldmann, Andreas Emil Nešetřil, Jaroslav Rzążewski, Paweł Computational Complexity Discrete Mathematics Combinatorics We examine ordered graphs, defined as graphs with linearly ordered vertices, from the perspective of homomorphisms (and colorings) and their complexities. We demonstrate the corresponding computational and parameterized complexities, along with algorithms associated with related problems. These questions are interesting, and we show that numerous problems lead to various complexities. The reduction from homomorphisms of unordered structures to homomorphisms of ordered graphs is proved, achieved with the use of ordered bipartite graphs. We then determine the NP-completeness of the problem of finding ordered homomorphisms of ordered graphs and the XP and W[1]-hard nature of this problem parameterized by the number of vertices of the image ordered graph. Classes of ordered graphs for which this problem can be solved in polynomial time are also presented. |
| title | Complexity Aspects of Homomorphisms of Ordered Graphs |
| topic | Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2511.23078 |