29
You should check the Hajós calculus. Hajós showed that every graph with chromatic number at least $k$ has a subgraph which has a "reason" for requiring $k$ colors. The reason in question is a proof system for requiring $k$ colors. The only axiom is $K_k$, and there are two rules of inference. See also this paper by Pitassi and Urquhart on the efficiency of ...
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-...
15
A partial answer, in that I don't know a nice "reason" that can be generalised, but the following graph (shameless nicked from here):
Isn't 3-colorable, but is obviously 4-colorable (being planar), and it contains no $K_{4}$, nor any cycle with a additional vertex connected to all the cycle vertices (unless I'm missing something, but the only vertices ...
13
There are several output-sensitive algorithms to enumerate all maximal cliques in polynomial time per output. One of the earliest algorithms was developed by Tsukiyama, Ide, Ariyoshi, and Shirakawa (1977).
Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, Isao Shirakawa: A New Algorithm for Generating All the Maximal Independent Sets. SIAM J. Comput. 6(3): 505-...
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 ...
12
Lovasz found topological obstructions for k-colorability and used his theory to solve Knaser's conjecture. His theorem is the following. Let G be a connected graph, and let N(G) be a simplicial complex whose faces are subsets of V that have a common neighbors. Then if N(K) is k-connected (namely, all its reduced homology groups are 0 up to dimension k-1) ...
12
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
Not having a large independent set can be as important as having a large clique.
An important obstruction for a graph to be non k-colorable is that the maximum size of an independent set is smaller than n/k, where n is the number of vertices. This is a very important obstraction. For example it implies that a random graph in G(n,1/2) has chromatic number at ...
11
Re your reformulation of the question as "More precisely, what I need is some theorem of the form: A graph $G$ has chromatic number $\chi(G)=k+1$ if and only if...":
I don't know whether you will think this is adequately explanatory, but it at least fits the syntax you request: an undirected graph $G$ has chromatic number $\chi(G)\ge k$ if and only if, no ...
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.
10
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)....
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.
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) ...
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
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 ...
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. ...
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 ...
6
The problem seems to be in $P$.
Take two vertices $u$, $v$ with distance exactly 3 (such a pair must exist when $p\ge 3$). They must have different colors (I will use R, G, B to denote 3 colors and the vertices in the same clique are colored the same color). Wlog assume $u$ is colored Red and $v$ is colored Green.
Now the rest of the vertices are ...
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
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
19.5k4 gold badges51 silver badges134 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
19.5k4 gold badges51 silver badges134 bronze badges
4
The algorithm of Bron–Kerbosch computes all maximal cliques in an undirected graph (see Wikipeadia). The worst-case running time is O(3n/3), apparently it is very fast in general and still is the fastest known algorithm to compute all maximal cliques. For a newer reference see the papers of V. Stix and Cazals and Karande.
Only top voted, non community-wiki answers of a minimum length are eligible
