Half-space separation in monophonic convexity
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917764998889472 |
|---|---|
| author | Elaroussi, Mohammed Nourine, Lhouari Vilmin, Simon |
| author_facet | Elaroussi, Mohammed Nourine, Lhouari Vilmin, Simon |
| contents | We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of vertices and asks whether these two sets can be separated by complementary convex sets, called half-spaces. While it is known this problem is $\mathbf{NP}$-complete for geodesic convexity -- the convexity of shortest paths -- we show that it can be solved in polynomial time for monophonic convexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_17564 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Half-space separation in monophonic convexity Elaroussi, Mohammed Nourine, Lhouari Vilmin, Simon Combinatorics Discrete Mathematics Data Structures and Algorithms We study half-space separation in the convexity of chordless paths of a graph, i.e., monophonic convexity. In this problem, one is given a graph and two (disjoint) subsets of vertices and asks whether these two sets can be separated by complementary convex sets, called half-spaces. While it is known this problem is $\mathbf{NP}$-complete for geodesic convexity -- the convexity of shortest paths -- we show that it can be solved in polynomial time for monophonic convexity. |
| title | Half-space separation in monophonic convexity |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.17564 |