On Computational Aspects of Ordered Matching Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918222152859648 |
|---|---|
| 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 | Ordered matchings, defined as graphs with linearly ordered vertices, where each vertex is connected to exactly one edge, play a crucial role in the area of ordered graphs and their homomorphisms. Therefore, we consider related problems from the complexity point of view and determine their corresponding computational and parameterized complexities. We show that the subgraph of ordered matchings problem is NP-complete and we prove that the problem of finding ordered homomorphisms between ordered matchings is NP-complete as well, implying NP-completeness of more generic problems. In parameterized complexity setting, we consider a natural choice of parameter - a number of vertices of the image ordered graph. We show that in contrast to the complexity context, finding homomorphisms if the image ordered graph is an ordered matching, this problem parameterized by the number of vertices of the image ordered graph is FPT, which is known to be W[1]-hard for the general problem. We also determine that the problem of core for ordered matchings is solvable in polynomial time which is again in contrast to the NP-completeness of the general problem. We provide several algorithms and generalize some of these problems into ordered graphs with colored edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23093 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Computational Aspects of Ordered Matching Problems Čertík, Michal Feldmann, Andreas Emil Nešetřil, Jaroslav Rzążewski, Paweł Computational Complexity Discrete Mathematics Combinatorics Ordered matchings, defined as graphs with linearly ordered vertices, where each vertex is connected to exactly one edge, play a crucial role in the area of ordered graphs and their homomorphisms. Therefore, we consider related problems from the complexity point of view and determine their corresponding computational and parameterized complexities. We show that the subgraph of ordered matchings problem is NP-complete and we prove that the problem of finding ordered homomorphisms between ordered matchings is NP-complete as well, implying NP-completeness of more generic problems. In parameterized complexity setting, we consider a natural choice of parameter - a number of vertices of the image ordered graph. We show that in contrast to the complexity context, finding homomorphisms if the image ordered graph is an ordered matching, this problem parameterized by the number of vertices of the image ordered graph is FPT, which is known to be W[1]-hard for the general problem. We also determine that the problem of core for ordered matchings is solvable in polynomial time which is again in contrast to the NP-completeness of the general problem. We provide several algorithms and generalize some of these problems into ordered graphs with colored edges. |
| title | On Computational Aspects of Ordered Matching Problems |
| topic | Computational Complexity Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2511.23093 |