2
$\begingroup$

In the notation of Garey and Johnson [1], two problems related to Ramsey Problem were defined:

$\textbf{ARROWING}$

Instance: (Finite) graphs $F$, $G$ and $H$.

Question: Does $F\rightarrow (G, H)$?

$\textbf{STRONG ARROWING}$

Instance: (Finite) graphs $F$, $G$ and $H$.

Question: Does $F\rightarrowtail(G, H)$?

Arrowing: given graphs $F$, $G$, $H$, does every edge-coloring of $F$ with red and blue contains either a red $G$ or a blue $H$?

This problem is $coNP$ for fixed $G$ and $H$, $\Pi_2^p$-complete (i.e. $coNP^{NP}$) [2] in general.

Strong Arrowingg: given graphs $F$, $G$, $H$, does every edge-coloring of $F$ with red and blue contains either a red $G$ or a blue $H$ as an Induced Subgraph? This version is also $\Pi_2^p$-complete in general [2].

However, the proof of Schaefer [2] relied heavily on constructing a suitable graph $F$, thus it is unlikely that a similar construction could be used for the case when $F$ is a complete graph. The computational complexity of determining Ramsey numbers is still open. Some discussions about this problem can be found in [3][4][5], but it is still not clear.

My question: what is the complexity of determining exact Ramsey Number? Can we find a PTAS of it?

As most of the existing related results highly depend on constructions, I am looking for the readers who are familiar with constructions (although a lot of constructions are not known where they are from) of Ramsey Number to give some hints or discussions. Suggestions and comments from TCS scientists are also highly welcome.

[1] Garey, Michael R., and David S. Johnson. "Computer and intractability." A Guide to the Theory of NP-Completeness (1979).

[2] Schaefer, Marcus. "Graph Ramsey theory and the polynomial hierarchy." Proceedings of the thirty-first annual ACM symposium on Theory of computing. ACM, 1999.

[3] Haanpää, Harri. Computational methods for Ramsey numbers. Helsinki University of Technology, 2000.

[4]Schweitzer, Pascal. Problems of unknown complexity: graph isomorphism and Ramsey theoretic numbers. Diss. Saarbrücken, Univ., Diss., 2009, 2009.

[5]Rosta, Vera. "Ramsey theory applications." The Electronic Journal of Combinatorics 1000 (2004): DS13-Dec.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ (1) It’s a function analogue of a sparse language (there is only one value for each input length), hence it cannot be hard for any of the usual classes like NP. (2) We don’t really know much about the Ramsey numbers. It’s perfectly possible they are given by a nice formula, computable in polynomial time. So, the best you can hope for are upper bounds. $\endgroup$
    – Emil Jeřábek
    Commented Apr 29, 2015 at 10:48
  • $\begingroup$ @EmilJeřábek, Thank you, Emil! For the sparse language, whether the encoding methods matter? In literature discussion, it seems that unary encoding and binary encoding can get different results for the Ramsey Number problem. $\endgroup$
    – user39815
    Commented Apr 29, 2015 at 15:10
  • $\begingroup$ Here is a post asking whether the exact formula exist for Ramsey Numbers. mathoverflow.net/questions/188114/… $\endgroup$
    – user39815
    Commented Apr 29, 2015 at 15:17
  • $\begingroup$ I am also wondering the approximate approach. But it seems that in combinatorial area, Asymptotic terms can be in different positions, however, in theoretical computer science, usually one considers approximation ratio. $\endgroup$
    – user39815
    Commented Apr 29, 2015 at 15:22
  • $\begingroup$ What I wrote was meant for unary input (which is the same as specializing the arrowing problems with complete graph as input). Of course, with binary input the problem just becomes exponentially harder (and in particular, the output has exponentially larger size than the input). $\endgroup$
    – Emil Jeřábek
    Commented Apr 30, 2015 at 11:20

0

Reset to default

You must log in to answer this question.