Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# 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 ...
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 ...

### 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

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

### 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$ ...
Accepted

### 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 ...
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 ...
Accepted

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

Feldman et al.  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 ...

### 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 ...
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.
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 ...
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 ...
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 ...