29
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 one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-...
13
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$ is the exponent for fast matrix multiplication. For 4-cycle-free graphs, plugging in $\omega<2.373$ and $m=O(n^{3/2})$ (else there is a $4$-cycle ...
13
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 have communicated this problem to many people, and taught it in cs266 at Stanford, due to its connection to solving $k$-Sat. (Several open problem sessions at ...
11
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 definition of $N$, CNF-SAT is basically solvable in $O(1.1279^N)$ time, as in the paper by Wahlstrom (link goes to a google scholar page of papers that cite it)....
10
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 lexicographically sorted order). In other words, $x_i$ is a "one-hot" encoding of the $i$th vertex in the clique (it is the characteristic vector for a set with one ...
10
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 Tarjan's decomposition.
9
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=(V,E)$ and $k$ construct the graph $G'$ with vertex set $V \times \{1,\dots,k\}$ and edges between $(v,i)$ and $(w,j)$ if $(i \ne j)$ and $(v \ne w)$ and $(v,w) ...
9
The Lovász $\vartheta$ function is an efficiently computable function with the property
$$
\alpha(G) \leq \vartheta(G) \leq \bar{\chi}(G),
$$
where $\alpha$ is independence number and $\bar{\chi}$ is clique cover number. If the bound $\frac{\bar{\chi}(G)}{\alpha(G)} \leq n^{1-\varepsilon}$ were true for some constant $\varepsilon > 0$, then we would have ...
9
I believe the most standard term is complete multipartite graph.
8
How about this:
Call your graphs simply $(K_1 + K_2)$-free graphs, where $K_n$
is the complete graph with $n$ vertices, + stands for disjoint union, and $H$-free means without $H$ as an induced subgraph.
8
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.
https://doi.org/10.1007/BF02760024
7
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 $(phase 1,i,j)$ in its state
In phase 2 it moves to some edge of the form $(i,m)$ or $(m,i)$ and assumes a state of the form $(phase 2,j,m)$
In phase 3, it checks ...
7
A similar hardness result is known for the inapproximability of chromatic number [1]. Independent set is hard to approximate as well, since it is $\mathsf{MAX\text{-}CLIQUE}$ on the complement graph. Some problems that are easier to approximate include vertex cover, (connected) dominating set, feedback vertex set, TSP and Steiner tree.
[1] Zuckerman, David. ...
6
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 is no polynomial time online algorithm for update (unless P=NP). If there is such an algorithm $A$, given a graph $G$, we can find a maximum clique of $G$ in ...
6
I recommend you taking a look at this book chapter:
J. L. Szwarcfiter, A Survey on Clique Graphs, Recent Advances in Algorithms and Combinatorics,
CMS Books in Mathematics 2003, pp 109-136.
In there, many characterizations of clique graphs of specific classes are given. For example, it is mentioned that the clique graphs of chordal graphs are the dually ...
6
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 and partitioned in polynomial time, and all valid partitions (if there are more than one) differ by only a single vertex and can also be found in polynomial time (...
5
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 particular the Clique problem is complete for $W[1]$ while Dominating Set is complete for $W[2]$, see the Wikipedia page for Parameterized Complexity. A reduction ...
5
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 $T(r)$ where you replace indeterminate $x_{ij}$ by $y_{ij}r^{a_{ij}+q/4}$, where $y_{ij}=y_{ji}$ is a uniformly and independently randomly chosen element in $F$ ...
5
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 is also a $k$-plex on $m$ vertices (for any $k$), we get that the size of the maximum $k$-plex is a $k$-approximation of the size of the maximum clique.
Since ...
5
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$ contain a $k$-clique?
Here is a construction that shows NP-completeness of your problem variant:
Let $G$ and $k$ be as in the proof in Garey and Johnson
Let $H_1$ ...
4
For unweighted problems, The Nearest Codeword problem in coding theory is known to be very hard to approximate. It is NP-hard to approximate to within
a factor $n^{ \Omega(1)/ \log \log n}$.
Another hard to approximate problem is the longest path problem in directed graphs. Björklund, Husfeldt, and Khanna showed that longest path in directed graphs is hard ...
answered Jun 12 '13 at 7:47
Mohammad Al-Turkistany
20.2k4 gold badges56 silver badges142 bronze badges
4
The title of this question does not match the content. As stated in the comments, there are some NP optimization problems for which any polynomial time approximation algorithm implies P = NP. Maybe you are looking for optimization problems that are not approximable within any polynomial factor, or that exhibit a threshold behavior? You may be looking for ...
4
Min TSP is harder to approximate than maximum clique. For the general case of Min TSP, it is hard to approximate the minimum weight of TSP within better than exponential factors.
answered Jun 10 '13 at 2:54
Mohammad Al-Turkistany
20.2k4 gold badges56 silver badges142 bronze badges
4
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.monash.edu.au/~davidwo/MillerMuller-NumberMaximalCliques.pdf
4
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 constructed graph is in fact $k$-partite.
So you get NP-hardness of deciding the existence of $k$-clique in $k$-partite graphs for free.
4
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.doi.org/10.1016/0022-0000(80)90060-4) which states that for every hereditary property $\Pi$ it is NP-hard to find, given a graph $G$, an induced subgraph of $G$ ...
4
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\{b,d\},\{a,b\},\{c,d\}\}$.
When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V_1\cup\{a,c\}$ and so on, so it is not hard ...
3
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.
3
Isn't the conjecture in the paper that the number of $(k+1)$-cliques in this case is at least $c^{k-1}$? That's the number you get by adding a single edge to the Turan-graph. I think it's proved in 1969-10. Also relevant: 1983-28.
Recently, there has been significant progress on bounding the number of cliques as a function of the quadratic term of the number ...
3
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 open.
Only top voted, non community-wiki answers of a minimum length are eligible
