29
votes
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 ...
- 26.2k
14
votes
Accepted
Complexity of k-clique for hypergraphs
It is not known if there is an $\varepsilon > 0$, $c > 2$, and $k > c$ such that $(c,k)$ hyperclique is in $n^{k-\varepsilon}$ time. Note that the case of $k \leq c$ is trivial. For years I ...
- 26.2k
13
votes
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$...
- 50.2k
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 ...
- 26.2k
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 ...
- 50.2k
10
votes
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 ...
- 10.3k
9
votes
Accepted
$k$-clique in $k$-partite graph
This should be indeed NP-hard. And the construction is very similar to one that already worked for a similar question: Many-one reduction from inequality problem to equality problem.
From a graph $G=(...
- 1,377
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.
...
- 1,721
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.
- 8,546
7
votes
Accepted
2FA state complexity of k-Clique?
It seems to me that triangles can be done by a 2FA $A$ with $O(n^2)$ state (n being the number of vertices).
For $k=3$ the idea is as follows:
In phase 1, $A$ chooses some edge $(i,j)$ and stores $(...
- 1,377
6
votes
Accepted
Algorithms for online clique detection
First of all I think you mean a maximum clique, not all cliques (and even not maximal cliques). As otherwise e.g in $K_n$ there are $2^n−1$ cliques.
If the question is the one that I said, then there ...
- 3,420
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 ...
- 50.2k
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 ...
- 13.5k
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$ ...
- 5,712
5
votes
Accepted
On Zero sum perfect matching
The problem is in RP in both (A) and (B) by a variation of Lovasz's algorithm:
Fix a finite field $F$ of characteristic $2$ on at least $q=4m\max_i |a_i|$ elements.
Consider the graph's Tutte matrix $...
- 3,244
5
votes
Accepted
Minimal polynomial reduction of dominating set to max clique
There are good reasons to expect that there is no polynomial time reduction that takes as input a graph $G$ and outputs a graph $\hat{G}$ such that $\omega(\hat{G})$ depends only on $\gamma(G)$. In ...
- 3,216
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 ...
- 1,821
4
votes
The number of cliques in a graph: the Moon and Moser 1965 result
Here is a copy of the 1965 paper by Moon and Moser: http://users.monash.edu.au/~davidwo/MoonMoser65.pdf
Note that the result was actually first proved in 1960 by Miller and Muller:
http://users....
- 41
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....
- 1,670
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 ...
- 5,712
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\...
- 328
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 ...
- 266
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 ...
- 50.2k
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 ...
- 3,160
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 ...
- 119
3
votes
Accepted
Counting the number of K4
The sum of all degrees $d(x)$ in a graph is at most $2e$. The sum of all $d(x)^{\alpha}$ is at most $(max degree)^{\alpha -1}$ times sum of all $d(x)$. Together these give the upper bound.
- 26.2k
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 ...
- 690
2
votes
Accepted
Comparison between the maximum clique and maximum biclique problem
Besides the recent W(1)-hardness result for the parametrized complexity of the biclique problem (pointed out by R B), here is a paper whose abstract gives some detailed information about the ...
- 4,584
2
votes
Accepted
Fast approximation of (vertex) clique cover
You can use a fast (e.g. greedy) max clique algorithm to find cliques one after another. That is, find a maximal clique, remove it from the graph, and repeat until the graph is empty. If fact, I just ...
- 136
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
...
- 5,712
Only top scored, non community-wiki answers of a minimum length are eligible