Share Your Experience: Take the 2024 Developer Survey

Tag Info

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[2]). But the algorithm you give in your question is subsumed by several other results. Using your ...
• 27.5k
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

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. ...
• 1,731
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.
• 8,691
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

Paritioning a graph into clique and independent set

Question (1) is easy polynomial time. As Juho has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the split graphs. They can be recognized ...

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$ ...
• 5,772
Accepted

Hardness of $k$-Plex

Lemma. If a graph has a $k$-plex on $m$ vertices, then it has a clique on $\frac m{k+1}$ vertices. Proof. Greedily pick the vertices of the clique from the $k$-plex. Since a clique on $m$ vertices ...
• 14k

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 ...
• 1,841

Maximum cliques of the transitive closure of a chordal DAG

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 ...
• 881