Skip to main content
Share Your Experience: Take the 2024 Developer Survey
11 votes

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 ...
Ryan Williams's user avatar
10 votes
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 ...
David Eppstein's user avatar
8 votes
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. ...
Yota Otachi's user avatar
  • 1,731
8 votes
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.
Lance Fortnow's user avatar
7 votes
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 ...
Command Master's user avatar
6 votes
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 ...
David Eppstein's user avatar
5 votes

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$ ...
Gamow's user avatar
  • 5,772
5 votes
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 ...
domotorp's user avatar
  • 14k
5 votes

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 ...
MassimoLauria's user avatar
4 votes

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 ...
Tassle's user avatar
  • 881
4 votes
Accepted

Minimal clique edge cover vs minimalist (assignment-minimum) ones

Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\...
Wei Zhan's user avatar
  • 903
4 votes
Accepted

Tree decompositions with unique witness for each edge

I'm afraid the answer to both of your questions is no. Consider a graph $(V_n, E_n)$ with $V_n = \{1,...,n+2\}$ and $E = \{\{i,i+1\} | 1 \leq i \leq n+1\} \cup \{\{i,i+2\} \mid 1 \leq i \leq n\}$. ...
Corto's user avatar
  • 56
4 votes

$k$-clique in $k$-partite graph

The book "Computers and Intractability" by Michael Garey and David S. Johnson contains a textbook NP-hardness proof for the $k$-clique problem. If you look into this proof, you will see that the ...
Gamow's user avatar
  • 5,772
4 votes

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....
Christian Komusiewicz's user avatar
3 votes
Accepted

Dividing a complete graph into two cliques with maximal sum of edge weights

I'm going to assume you didn't mean to end up two (maximal) cliques, but instead two disconnected complete graphs. Those are not the same, e.g. for $n = 6$ you can end up with extra edges that don't ...
orlp's user avatar
  • 885
3 votes
Accepted

Will core decomposition get a maximal clique?

No. The illustration shows a graph (the graph of a cube with one corner truncated) and a valid removal sequence such that the vertices left at the point when the minimum degree equals $|S|-1$ (the two ...
David Eppstein's user avatar
3 votes
Accepted

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

Feldman et al. [1] give several references to methods for e.g., finding cliques of size $k = \Omega(\sqrt{n})$, including spectral methods, SDPs, combinatorial methods, nuclear norm minimization, and ...
Juho's user avatar
  • 3,170
3 votes

Reference Request: complexity results on finding $(1+\epsilon) \log n$ size clique in $G(n,1/2)$

To answer the first part of your question, a conjecture in Karp'76 states that there is no efficient algorithm to find cliques of size $(1+ \epsilon)\log(n)$ for $G(n, 1/2)$. This conjecture is still ...
Ainesh Bakshi's user avatar
3 votes
Accepted

Approximation algorithm for balanced bipartite independent set?

There is a nice reduction by Chalermsook et al. (WG 2020) that can give the kind of approximation you want. I'll describe it below in terms of finding balanced complete bipartite subgraph (biclique) ...
Pasin Manurangsi's user avatar
2 votes

Max weight k-clique

Your problem is very hard to approximate, even in the case where all weights are just $0$ or $1$: Pasin Manurangsi: Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph ...
Gamow's user avatar
  • 5,772
1 vote

Maximum cliques of the transitive closure of a chordal DAG

A linear bound is impossible. Suppose your graph is a star, with half of the edges oriented towards the universal vertex $u$ and the rest oriented outward. In the transitive closure, the maximal ...
Vinicius dos Santos's user avatar
1 vote
Accepted

approximate maximum clique given vertex cover

Since it is asymptotic approximation and epsilon is a constant, for OPT big enough being 1 off is always good. Let's put it another way. Either your optimal is smaller than 1/epsilon and you can find ...
Nicolas GZ's user avatar
1 vote

Algorithms for finding all cliques of a given degree in a graph

This maybe: https://papers-gamma.link/paper/32 With an open source implementation here: https://github.com/maxdan94/kClist
maxdan94's user avatar
  • 563
1 vote

Finding All Cliques of an Undirected Graph

If C is a maximal clique, any subset is a clique, ie the set of cliques in a graph forms an independent system. If the independent system $\mathcal{I}$ on ground set $V$ is given by an oracle $O$ ...
M. kanté's user avatar
  • 1,046
1 vote
Accepted

Maximal Clique partition of vertices with smallest number of cut edges

This problem is the Cluster Edge Deletion problem. Given a graph $G = (V,E)$ and an integer, can we delete at most $k$ edges $F \subseteq E$ such that $G-F$ is a cluster graph? A cluster graph ...
Pål GD's user avatar
  • 550
1 vote

Finding cliques in a big graph

The 1985 paper by Nešetřil and Poljak linked in this answer to a similar question suggests that you can search for the subgraph $K_{3\ell+i}$ in time $O(n^{i+\ell ω})$, where $ω$ is the matrix ...
Max Merz's user avatar
  • 111

Only top scored, non community-wiki answers of a minimum length are eligible