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

Hot answers tagged

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 ...
user avatar
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 ...
user avatar
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$...
user avatar
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 ...
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 ...
user avatar
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 ...
user avatar
  • 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=(...
user avatar
  • 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. ...
user avatar
  • 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.
user avatar
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 $(...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 $...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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....
user avatar
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....
user avatar
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 ...
user avatar
  • 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\...
user avatar
  • 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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
user avatar
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.
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 5,712

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