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 ...
- 27.3k
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.9k
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 ...
- 27.3k
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.9k
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 ...
- 11.7k
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,616
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,731
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 ...
- 464
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,417
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.9k
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.9k
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,254
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,831
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,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....
- 1,700
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 ...
- 691
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\...
- 723
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,772
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 ...
- 720
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.9k
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
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) ...
- 306
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,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 ...
- 1,868
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 ...
- 26
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
- 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$ ...
- 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 ...
- 548
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 ...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible