EUVIMEDEUVIMED entdecken
Crossref

Finding forest-orderings of tournaments is NP-complete

Pierre Aboulker, Guillaume Aubian, Raul Lopes

Discrete Mathematics & Theoretical Computer Science · 21.07.2026 · vol. 28:2 (Graph Theory)

DOI: 10.46298/dmtcs.14281 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 21.07.2026. Verfasst von Pierre Aboulker und 2 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a class of (undirected) graphs $\mathcal{C}$, we say that a Feedback Arc Set (FAS for short) $F$ is a $\mathcal{C}$-FAS if the graph induced by the edges of $F$ (forgetting their orientations) belongs to $\mathcal{C}$. We show that deciding if a tournament has a $\mathcal{C}$-FAS is NP-complete when $\mathcal{C}$ is the class of all forests. We are motivated by connections between $\mathcal{C}$-FAS and structural parameters of tournaments, such as the dichromatic number, the clique number of tournaments, and the strong Erdős-Hajnal property.

Zitieren

APA

Aboulker, P., Aubian, G., & Lopes, R. (2026). Finding forest-orderings of tournaments is NP-complete. Discrete Mathematics & Theoretical Computer Science, vol. 28:2(Graph Theory). https://doi.org/10.46298/dmtcs.14281

Vancouver

Aboulker P, Aubian G, Lopes R. Finding forest-orderings of tournaments is NP-complete. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:2(Graph Theory). doi:10.46298/dmtcs.14281

BibTeX
@article{Aboulker2026,
  author = {Aboulker, Pierre and Aubian, Guillaume and Lopes, Raul},
  title = {Finding forest-orderings of tournaments is NP-complete},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:2},
  number = {Graph Theory},
  doi = {10.46298/dmtcs.14281}
}
Kostenlos starten →