A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Hot answers tagged

12

Recalling that a clique is a subset $C$ of vertices of an undirected graph such that the subgraph induced by $C$ is fully connected. That is, every two distinct vertices in $C$ are connected by a distinct edge of the graph. This means different edges, not the same. So, on a clique $C$ containing $k$ vertices $v_1, v_2,..,v_k$, there are $\frac{k(k-1)}2$ ...


7

Consider an instance $(G,k)$ of the clique problem: deciding whether there is a clique of size $k$ in the graph $G$. Construct a course for each vertex (say "vertex course") and for each edge (say "edge course") in $G$. Each edge course has two precondition vertex courses corresponding to its two endpoints. In addition, we set $m_1=k,m_2=+\infty, m_3=m-\...


6

When $c > \sqrt{n}$, you add an independent set of size $m$ so that $c = \sqrt{n+m}$ (i.e., you need $m = c^2-n$). When $c < \sqrt{n}$, try doing the same, increasing both $n$ and $c$ at the same time, by adding a complement of an independent set. (You might need to add a few isolated vertices as well.)


6

Let $G=(V,E)$ be the bipartite graph. Construct a new graph $G'=(V',E')$ whose vertices are the edges of $G$, and where we add $(e,e')$ to $E'$ if $e,e'$ are two edges from $G$ that don't touch each other (don't have an endpoint in common). Now there's a matching of size $s$ in $G$ if and only if there's a clique of size $s$ in $G'$. In particular, there'...


6

The probability that a specific set of size $k$ is independent is exactly $(1-p)^{\binom{k}{2}}$ (why?). Linearity of expectation shows that the expected number of independent sets of size $k$ is $\binom{n}{k} (1-p)^{\binom{k}{2}}$ (why?). If you can't follow this calculation, please follow Denis Pankratov's advice and look up linearity of expectation and ...


6

Although I don't know the name for such problem, I can show this problem is NP-hard. For a triangle free graph, all equivalence classes must be a matching. The minimum number of equivalence classes that covers the graph equals the chromatic index of the graph. According to this article, finding the chromatic index for a triangle free graph is NP-complete.


5

Thus I'm still curious if there are other more efficient approaches to solving the problem. If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem. Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$. The problem is para-NP-hard in the unweighted case and the problem is just ...


5

No, you couldn't say that, because it's not true. A helpful method is to prove all your claims. Don't just guess -- try to find a proof. If you're struggling to find a proof, the first thing to check is whether maybe the thing you're trying to prove is false, so look for a counterexample. In this case you should easily be able to find a counterexample to ...


5

The problem is equivalent to deciding whether the complement graph of $G$ has a bipartition $(A,B)$ such that $|A|=|B|$. In order to check if such a bipartition exists, one can first compute an arbitrary bipartition $(A,B)$. If no such bipartition exists, we are finished. If it does exists, we must check whether we can flip single connected components of ...


4

The problem is solvable in polynomial time, using the following algorithm: Keep removing pairs of unconnected vertices, until a clique remains. If the graph has a clique of size $(3/4)n$, then the clique you end up with contains at least $n/4$ vertices (exercise). Source: Boppana and Halldórsson, Alon and Kahale.


4

The problem is known as the equivalence covering problem in graph theory. It is upper bounded by the clique covering number (the minimum collection of cliques such that each edge of the graph is in at least one clique). There are many similar problems and definitions; one has to be very careful here. These two numbers are denoted by $\text{eq}(G)$ and $\text{...


4

The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of ordered cliques, that is, the number of ordered sequences of distinct vertices which form cliques. In particular, if the graph is complete then the number of recursive calls is $$ \sum_{...


4

It's a matter of logical quantifiers. Consider this statement: "if every natural number $n$ is bounded above by a constant $c$, how come there is no constant $c$ that bounds every natural number $n$ by above?". The above is an example where $\forall n.\ \exists c.\ \ldots$ does not imply $\exists c.\ \forall n.\ \ldots$. Indeed, in the former, we can ...


4

A graph is bipartite if and only if it is 2-colorable. A clique of size at least 3 contains a triangle, and a triangle $K_3$ clearly cannot be colored with 2 colors. It follows we can't find a triangle in a bipartite graph, so the corresponding decision problem is very easy for a bipartite graph.


4

Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex in the bipartite graph has degree $n/3$. Your algorithm would thus remove all the vertices in the clique. The remaining graph is bipartite, and so its maximal ...


4

Create a new graph whose vertices are pairs of vertices in the original graph (optimization: 2-cliques, i.e. edges, in the original graph), and whose edges correspond to 4-cliques. The new graph has a 3-clique iff the original graph has a 6-clique (why?).


3

The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of $$ \sum_{k=1}^n n^k, $$ which is no longer polynomial.


3

The high-level idea is this: the existence of a triangle in $H$ corresponds to the existence of a clique of size $3\ell$ in $G$, and we know how to detect triangles using matrix multiplication. So let $\ell$ indeed be divisible by three. The auxiliary graph $H$ has a vertex for every $K_\ell$, and an edge between two vertices precisely when the ...


3

In fact, NP is not the set of problems that are easy to verify but hard to solve. It is just the set of problems that are easy to verify. NPC, the set of NP-complete problems, is the set of problems that are easy to verify but seem hard to solve. Your problem is in NP but it isn't NP-complete (unless P=NP), since it's also in P. That is, it can be solved in ...


3

You are using generate for two different actions, your second bullet is not explained correctly, and your third bullet always fails. Here is a better version of your algorithm: Non-deterministically generate a list of $k$ distinct nodes of $G$: $v_1,\ldots,v_k$. Calculate the $k\times k$ matrix $B$ given by $B(i,j) = A(v_i,v_j)$, where $A$ is the adjacency ...


3

Since $\mu$ is the sum of $n$ terms, we can estimate it up to a factor of $n$ by the maximal term: $$ \max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq \sum_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq n\max_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d}. $$ In order to find out which term is the largest, we can use the estimate $...


3

A problem $P$ being NP-hard means that all problems in NP can be reduced to $P$. That's by definition. Working out the exact reduction needed can be tricky, which is why one usually looks for a somehow similar problem to prove hardness. You probably wouldn't try to directly reduce MINIMUM INTERVAL GRAPH COMPLETION to Tetris to prove its hardness. In ...


3

I am assuming you mean the number of maximal cliques, as the number of cliques of a complete graph is trivially $2^n$ (any subset of the vertices forms a clique). For the number of maximal cliques, take the complement of a disjoint union of triangles. Since the number of maximal independent sets is exactly the same (in the complement), you can count the ...


3

Suppose that there exists a polytime algorithm which finds a clique of size $n^\epsilon$ if there is any. Then you can approximate maximum clique to within $n^{1-\epsilon}$ (assuming $\epsilon \leq 1/2$), which is NP-hard by a classical result of Håstad. Indeed, run your algorithm (stopping it if it exceeds its advertized running time), and check whether its ...


3

I believe this is FPT. FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement. This is equivalent to finding a vertex cover of size $k$. And the latter is FPT.


3

The value is $2\log_2 n - 2\log_2\log_2 n + O(1)$. Let $k_0$ be the maximal value such that the expected number of cliques of size $k_0$ is at least 1. A boring calculation shows that $k_0 = 2\log_2 n - 2\log_2\log_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k_0-1)$-clique. This implies that $k > k_0-1$. On ...


3

The graphs with clique size at least $k$ and VC at most $k$ have a particular structure: They can be partitioned into three sets, $C$, $I$ and a singleton $\{s\}$; $G[C]$ is a clique, $G[I]$ is an independent set and $s$ is just a vertex. $G[C \cup I]$ is what's called a split graph. Proof: If a graph $G$ contains a clique of size $k$, then that clique ...


3

A maximal clique and a maximum clique are in general different. A set of vertices $S$ is a maximal clique if $S$ is a clique and you cannot add any vertex to $S$ such that the resulting set would form a clique. The set $S$ forms a maximum clique when there is no other set of vertices that forms a clique that is larger than $S$. You mention bipartite graphs, ...


3

The simplest NP-hardness reduction is as follows. Suppose we are given an instance $(G,k)$ of CLIQUE. If $k \leq c$ then we solve CLIQUE by brute force in time $O(n^c)$. Otherwise, $G$ has a $k$-clique iff it has a $k$-clique consisting of super-connectors. This is because any vertex in a $k$-clique must have degree at least $k-1 \geq c$, and so is a super-...


3

This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.


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