DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.25

The Complexity of Ramsey Arrowing: A Computational Approach for Hardness Proofs

Authors: Zohair Raza Hassan

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

Abstract

In graph Ramsey theory, the arrowing operator is used to describe the appearance of unavoidable substructures within colored graphs; for graphs G, F, and H, we say G → (F,H) (read, G arrows F, H) if every red/blue coloring of G’s edges contains a red F or a blue H. For fixed F and H, the (F,H)-Arrowing problem asks whether G → (F,H) for some given graph G. (F,H)-Arrowing has been shown to be in P or coNP-complete for different pairs (F,H). However, categorizing the complexity for all pairs still remains wide open. In general, categorizing the complexity of problems whose nature depends on some underlying graph - or, in our case, pair of graphs - is a daunting task, and (F,H)-Arrowing is no exception. Hardness proofs typically rely on ad-hoc, laborious constructions of special graphs known as "gadgets." In this work, we present a simple, computational approach to find these gadgets for small (F,H)-Arrowing problems and show how these can be extended to other (F,H)-Arrowing problems. Our main focus is on the simplest case for which the complexity remains uncategorized: F = P₃. We showcase the efficacy of our computational approach by presenting hardness proofs for (P₃, H)-Arrowing problems previously not known to be coNP-hard. Moreover, we show how to generalize hardness to other (P₃,H)-Arrowing problems by either: (1) carefully inspecting and modifying our found gadgets, or (2) coming up with intuitive constructions to reduce (P₃, H')-Arrowing to (P₃, H)-Arrowing, where H' is a subgraph of H. We also discuss how our methodology can be extended to work for other (F,H)-Arrowing problems by showing new results for F = P₄ and K_{1,3}. We see our work as an important step towards categorizing the complexity of (F,H)-Arrowing for all pairs (F,H). (F,H)-Arrowing is thought to be hard when (F',H')-Arrowing is hard where F' and H' are subgraphs of F and H, respectively. Under this assumption, our results narrow down the only uncategorized family of problems for which the problem may lie in P. Beyond the complexity of (F,H)-Arrowing, we believe that the broader impact of our work is showing how computational methodologies can be adopted for proving hardness, and we hope our approach will be adopted to find gadgets for other open graph problems as well.

Cite as

Zohair Raza Hassan. The Complexity of Ramsey Arrowing: A Computational Approach for Hardness Proofs. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hassan:LIPIcs.WG.2026.25,
  author =	{Hassan, Zohair Raza},
  title =	{{The Complexity of Ramsey Arrowing: A Computational Approach for Hardness Proofs}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{25:1--25:20},
  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.25},
  URN =		{urn:nbn:de:0030-drops-261916},
  doi =		{10.4230/LIPIcs.WG.2026.25},
  annote =	{Keywords: Graph Arrowing, Ramsey theory, Hardness reductions, Computational proofs}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.59

The Complexity of (P₃, H)-Arrowing and Beyond

Authors: Zohair Raza Hassan

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

Often regarded as the study of how order emerges from randomness, Ramsey theory has played an important role in mathematics and computer science, giving rise to applications in numerous domains such as logic, parallel processing, and number theory. The core of graph Ramsey theory is arrowing: For fixed graphs F and H, the (F,H)-Arrowing problem asks whether a given graph, G, has a red/blue coloring of the edges of G such that there are no red copies of F and no blue copies of H. For some cases, the problem has been shown to be coNP-complete, or solvable in polynomial time. However, a more systematic approach is needed to categorize the complexity of all cases. We focus on (P₃,H)-Arrowing as F = P₃ is the simplest meaningful case for which the complexity question remains open, and the hardness for this case likely extends to general (F,H)-Arrowing for nontrivial F. In this pursuit, we also gain insight into the complexity of a class of matching removal problems, since (P₃,H)-Arrowing is equivalent to H-free Matching Removal. We show that (P₃,H)-Arrowing is coNP-complete for all 2-connected H except when H = K₃, in which case the problem is in P. We introduce a new graph invariant to help us carefully combine graphs when constructing the gadgets for our reductions. Moreover, we show how (P₃,H)-Arrowing hardness results can be extended to other (F,H)-Arrowing problems. This allows for more intuitive and palatable hardness proofs instead of ad-hoc constructions of SAT gadgets, bringing us closer to categorizing the complexity of all (F,H)-Arrowing problems.

Cite as

Zohair Raza Hassan. The Complexity of (P₃, H)-Arrowing and Beyond. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 59:1-59:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hassan:LIPIcs.MFCS.2024.59,
  author =	{Hassan, Zohair Raza},
  title =	{{The Complexity of (P₃, H)-Arrowing and Beyond}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{59:1--59:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.59},
  URN =		{urn:nbn:de:0030-drops-206153},
  doi =		{10.4230/LIPIcs.MFCS.2024.59},
  annote =	{Keywords: Graph arrowing, Ramsey theory, Complexity}
}

Search Results

Documents authored by Hassan, Zohair Raza

The Complexity of Ramsey Arrowing: A Computational Approach for Hardness Proofs

Abstract

Cite as

The Complexity of (P₃, H)-Arrowing and Beyond

Abstract

Cite as

Thanks for your feedback!

Could not send message