DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.22

A Note on the Complexity of Directed Clique

Authors: Grzegorz Gutowski and Mikołaj Rams

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

For a directed graph G, and a linear order ≪ on the vertices of G, we define the backedge graph G^≪ to be the undirected graph on the same vertex set with edge {u,w} in G^≪ if and only if (u,w) is an arc in G and w ≪ u. The directed clique number of a directed graph G is defined as the minimum size of the maximum clique in the backedge graph G^≪ taken over all linear orders ≪ on the vertices of G. A natural computational problem is to decide for a given directed graph G and a positive integer t, if the directed clique number of G is at most t. This problem has polynomial algorithm for t = 1 and is known to be NP-complete for every fixed t ≥ 3, even for tournaments. In this note we prove that this problem is Σ^𝖯₂-complete when t is given on the input.

Cite as

Grzegorz Gutowski and Mikołaj Rams. A Note on the Complexity of Directed Clique. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 22:1-22:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gutowski_et_al:LIPIcs.WG.2026.22,
  author =	{Gutowski, Grzegorz and Rams, Miko{\l}aj},
  title =	{{A Note on the Complexity of Directed Clique}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{22:1--22:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.22},
  URN =		{urn:nbn:de:0030-drops-261885},
  doi =		{10.4230/LIPIcs.WG.2026.22},
  annote =	{Keywords: Directed Clique, Computational Complexity, Polynomial Hierarchy}
}

Search Results

Documents authored by Rams, Mikołaj

A Note on the Complexity of Directed Clique

Abstract

Cite as

Thanks for your feedback!

Could not send message