DROPS

Document

DOI: 10.4230/LIPIcs.SAND.2026.7

Extending Ghouila-Houri’s Characterization of Comparability Graphs to Temporal Graphs

Authors: Pierre Charbit, Michel Habib, and Amalia Sorondo

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract

An orientation of a static graph is called transitive if for any three vertices a,b,c, the presence of arcs (a,b) and (b,c) forces the presence of arc (a,c). If only the presence of an arc between a and c is required, but its orientation is unconstrained, the orientation is called quasi-transitive. A fundamental result due to Ghouila-Houri [Ghouila-Houri, 1962] states that any static graph admitting a quasi-transitive orientation also admits a transitive orientation. In a seminal work [Mertzios et al., 2025], Mertzios et al. introduced the notion of temporal transitivity in order to model information flows in simple temporal networks. We revisit the model introduced by Mertzios et al. and propose an analogous to Ghouila-Houri’s characterization for the temporal scenario. We present a structural theorem that will allow us to express by a 2-SAT formula all the constraints imposed on a temporal graph for it to admit a temporal transitive orientation. The latter produces an efficient recognition algorithm for graphs admitting such orientations, that we will call comparability temporal graphs. Inspired by the lexicographic strategy presented by Hell and Huang in [Hell and Huang, 1995] to transitively orient static graphs, we then propose an algorithm for constructing a temporal transitive orientation of a YES instance. This algorithm is straightforward and has a running-time complexity of O(nm + min{kn,m²}), with n, m and k being respectively the number of vertices, edges and monolabel triangles, i.e., triangles having the same unique time-label on their edges, in the temporal graph. This represents an improvement compared to the algorithm presented in [Mertzios et al., 2025]. Additionally, we extend the temporal transitivity model to temporal graphs having multiple time-labels associated to their edges and claim that the previous results hold in the multilabel setting. Finally, we propose a characterization of comparability temporal graphs by forbidden temporal ordered patterns.

Cite as

Pierre Charbit, Michel Habib, and Amalia Sorondo. Extending Ghouila-Houri’s Characterization of Comparability Graphs to Temporal Graphs. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{charbit_et_al:LIPIcs.SAND.2026.7,
  author =	{Charbit, Pierre and Habib, Michel and Sorondo, Amalia},
  title =	{{Extending Ghouila-Houri’s Characterization of Comparability Graphs to Temporal Graphs}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.7},
  URN =		{urn:nbn:de:0030-drops-262416},
  doi =		{10.4230/LIPIcs.SAND.2026.7},
  annote =	{Keywords: Temporal graphs, Transitive orientations, Graph algorithms}
}

Document

DOI: 10.4230/LIPIcs.IPEC.2018.17

Parameterized Complexity of Independent Set in H-Free Graphs

Authors: Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Abstract

In this paper, we investigate the complexity of Maximum Independent Set (MIS) in the class of H-free graphs, that is, graphs excluding a fixed graph as an induced subgraph. Given that the problem remains NP-hard for most graphs H, we study its fixed-parameter tractability and make progress towards a dichotomy between FPT and W[1]-hard cases. We first show that MIS remains W[1]-hard in graphs forbidding simultaneously K_{1, 4}, any finite set of cycles of length at least 4, and any finite set of trees with at least two branching vertices. In particular, this answers an open question of Dabrowski et al. concerning C_4-free graphs. Then we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques. We also provide a framework for solving several other cases, which is a generalization of the concept of iterative expansion accompanied by the extraction of a particular structure using Ramsey's theorem. Iterative expansion is a maximization version of the so-called iterative compression. We believe that our framework can be of independent interest for solving other similar graph problems. Finally, we present positive and negative results on the existence of polynomial (Turing) kernels for several graphs H.

Cite as

Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, and Rémi Watrigant. Parameterized Complexity of Independent Set in H-Free Graphs. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.IPEC.2018.17,
  author =	{Bonnet, \'{E}douard and Bousquet, Nicolas and Charbit, Pierre and Thomass\'{e}, St\'{e}phan and Watrigant, R\'{e}mi},
  title =	{{Parameterized Complexity of Independent Set in H-Free Graphs}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.17},
  URN =		{urn:nbn:de:0030-drops-102183},
  doi =		{10.4230/LIPIcs.IPEC.2018.17},
  annote =	{Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs}
}

Search Results

Documents authored by Charbit, Pierre

Extending Ghouila-Houri’s Characterization of Comparability Graphs to Temporal Graphs

Abstract

Cite as

Parameterized Complexity of Independent Set in H-Free Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message