# Tag Info

Accepted

### Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

Yes, this is known. It appears in one of the must-cite references on triangle finding... Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most ...

### Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?

It's not quadratic, but Alon Yuster and Zwick ("Finding and counting given length cycles", Algorithmica 1997) give an algorithm for finding triangles in time $O(m^{2\omega/(\omega+1)})$, where $\omega$...

### On reducing the hardness of CNF-SAT to k-Clique

I don't know the answer to your specific question (it seems related to the question of whether W1=W). But the algorithm you give in your question is subsumed by several other results. Using your ...
Accepted

### Tree-decomposition with clique interfaces

See "Decomposition by clique separators", Robert E. Tarjan, Discrete Mathematics 55 (2): 221–232, 1985. If I understand correctly, your notion of width is essentially the size of the largest piece in ...
Accepted

### Improving Cook's generic reduction for Clique to SAT?

You can express $k$-clique as a SAT instance with $O(nk)$ variables and $O(nk^2)$ clauses. For fixed $k$, this is linear in $n$. Let $x_{iv}=1$ if $v$ is the $i$th vertex in the clique (by ...
Accepted

### Separating 2-SAT from Clique

2-SAT is NL-complete so separating 2-SAT from Clique would separate NP from NL, also a major open problem.
Accepted

### Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph. ...
Accepted

### clique problem in graphs with bounded degree

No (unless $\text{P}=\text{NP}$), it can be solved in polynomial time. For each vertex, if it is of degree $d-2$ or less it can't be in a clique, and we can skip it. If it is of degree $d-1$ there is ...
Accepted

### Separating 2-SAT from Clique

I think there is at least one model of computation where 2-SAT is easy and Clique is provably hard: resolution refutation complexity (i.e. how hard is to deduce contradiction from the initial clauses ...

### Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete: Instance: An integer $k$; a $k$-partite graph $G=(V,E)$ Question: Does $G$ ...

### Hardness of $k$-Plex

The property of being a $k$-plex is hereditary, that is, closed under vertex deletion. Therefore, the NP-hardness for every fixed $k$ follows from a general result of Lewis and Yannakakis (http://dx....
I think you can extend Vinicius dos Santos' idea to show that no polynomial bound is possible. Consider a graph on $n$ vertices divided into $d\geq 1$ groups of size about $n/d$ as follows: Its ...