Is it correct to say that the Clique Problem is in $ P$ iff there exists a family of Boolean circuits $ C$ to decide Clique whose sizes are bounded by a polynomial? And based on this question, does that imply that there exists an equivalent set of Boolean formulas $ F$ to decide Clique whose sizes are bounded by a polynomial? And if there is such an $ F$ , would there be correct derivations based on propositional logic axioms from any member of $ F$ to the corresponding large naive formula for Clique?

# Tag: clique

## Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

Is the k-Clique Problem (given a Graph G and a natural number k does G kontain a Clique of size k)

polynomial time reduzible to the graph-Homomorphism Problem (given two graphs, G and H, is there a Homomorphism from G to H)

And if so what would the reduction look like?

Since i am a little confused by the subject, is the following correct?

A polynomial time reduction from Clique to graph-Homomorphism is a funktion that can be calculated in polynomial time and for which if you input a yes instance of clique it returns a yes instance of graph-Homomorphism, same for no instances.

## Minimum Clique Cover – Mixed Integer Programming

I have a general (undirected) graph with a set of nodes, a set of edges, and a weight for each edge. I want to find a minimum clique cover of the graph, that is, a partition of the graph into the smallest number of cliques. I also want to maximize the sum of edge weights over the cliques. I want to use an integer programming approach for this problem.

Can any one give me some hints or some references that use mixed integer linear programming for the (maximum weight) minimum clique partition?

Thank you very much.

## Polynomial-time algorithm for Clique partition

Reductions for showing algorithms. The following fact is true: there is a polynomial-time algorithm BIP that on input a graph 𝐺 = (𝑉 , 𝐸) outputs 1 if and only if the graph is bipartite: there is a partition of 𝑉 to disjoint parts 𝑆 and 𝑇 such that every edge (𝑢, 𝑣) ∈ 𝐸 satisfies either 𝑢 ∈ 𝑆 and 𝑣 ∈ 𝑇 or 𝑢 ∈ 𝑇 and 𝑣 ∈ 𝑆. Use this fact to prove that there is polynomial-time algorithm to compute that following function CLIQUEPARTITION that on input a graph 𝐺 = (𝑉 , 𝐸) outputs 1 if and only if there is a partition of 𝑉 the graph into two parts 𝑆 and 𝑇 such that both 𝑆 and 𝑇 are cliques: for every pair of distinct vertices 𝑢, 𝑣 ∈ 𝑆, the edge (𝑢, 𝑣) is in 𝐸 and similarly for every pair of distinct vertices 𝑢, 𝑣 ∈ 𝑇 , the edge (𝑢, 𝑣) is in

## CLIQUE $\leq_p$ SAT

i’m trying to reduce CLIQUE to SAT:

- Given: Graph G=(Vertices V, Edges E) and $ k \in \mathbb{N}$
- Output: Formular F such that if G contains a complete subgraph of size k, the formular is satisfiable (and vice versa).

I tried doing it the way Cook/Levin showed that SAT is NP-complete by introducing a set of booleans $ v_i$ for each vertex and $ e_{i, j}$ for an edge going from $ v_i$ to $ v_j$ . Now if $ v_i$ is part of the clique, then $ e_{i, j}$ must be true iff $ v_j$ is also in the clique.

So we can conclude, that $ v_i \land v_j \implies e_{i, j}$ and this is for true for at least $ i, j \in \{0, …, k – 1\}$ and $ i \neq j$ . Also we need to make sure that no edge that doesn’t exist can be set to true: $ \bigwedge_{(i, j)\notin E} \lnot\, e_{i, j}$ .

I don’t know if im on the correct way or if I might miss something.

- How would I restrict the formular $ v_i \land v_j \implies e_{i, j}$ to be true for at least k variables?
- Is this way in poly-time?
- Is there any better way?

## Javascript – Trocar a Imagem com Um Clique em Vários Registros

Olá, pessoal!!!

Estou com um pequeno problema em Javascript. Tenho uma tabela com várias linhas, em cada linha tem dados e um Check no final da linha que, quando clicado, muda a imagem. Muito similar as listagem do Joomla, quem conhece, entenderá!!!!

Até consegui, aqui mesmo o script que muda a imagem, mas, muda em uma linha só. Como fazer para que o evento ocorra em todas as linhas???

Segue o Código:

` function test() { if (document.pic1.src == 'https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Tick_Mark_Dark-32.png') { document.pic1.src = 'https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Close_Icon_Dark-32.png'; } else if (document.pic1.src == 'https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Close_Icon_Dark-32.png') { document.pic1.src = 'https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Tick_Mark_Dark-32.png'; } }`

`<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Document</title> </head> <body> <form action="#"> <table> <tr> <td>Zé Mané</td> <td> <img name="pic1" src="https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Tick_Mark_Dark-32.png" onclick="test()" /> </td> </tr> <tr> <td>João das Paçocas</td> <td> <img name="pic2" src="https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Tick_Mark_Dark-32.png" onclick="test()" /> </td> </tr> <tr> <td>Carlão Pé de Burro</td> <td> <img name="pic3" src="https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Tick_Mark_Dark-32.png" onclick="test()" /> </td> </tr> <tr> <td>Zezão Mão de Entortar Cano</td> <td> <img name="pic4" src="https://cdn3.iconfinder.com/data/icons/flat-actions-icons-9/792/Tick_Mark_Dark-32.png" onclick="test()" /> </td> </tr> </table> </form> </body> </html>`

Quem puder me dizer como faço, desde já agradeço.

## Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an edge would create a clique of size k. What is an efficient algorithm that can complete this task, and what is the time complexity?

## Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time?

Having an undirected graph, I am trying to partition all its vertices into cliques so that the number of cliques is the smallest. The problem can be formulated as an integer program, where every vertex corresponds to an integer variable (index of its clique), and the objective function is to minimize the sum of all these variables. For every edge *not* in the graph, a condition is created to ensure the corresponding vertex variables are not equal, like this:

$ $ b_k \in \{0, 1\}$ $ $ $ x_i – x_j + M*b_k >= 1$ $ $ $ x_j – x_i + M*(1-b_k) >= 1$ $

$ b_k$ indicates the relation between the values of $ x_i$ and $ x_j$ . With a sufficiently large $ M$ , one of the conditions is always true, in which case the other one ensures the distance between the values is at least 1.

However, this approach seems to have exponential complexity, making it work only on very small graphs.

Assuming the number of cliques is expected to be small, and usually no edges exist across cliques, is there a better approach to this problem? I am thinking about finding the maximum independent set first and use it to fix certain variables (since they are guaranteed to be in different cliques). Will that help in increasing the speed?

## Clique of constant size

It is well known that Clique is a $ NP$ -Complete problem, But given some constant value $ K$ , finding whether a graph $ G$ has a clique of size $ K$ , is always a log-space ($ L$ ) class problem?

## Reducing CLIQUE to Super Connector problem

I am trying to show that our problem is NP-Complete by reducing the known problem CLIQUE to our problem.

Regular CLIQUE problem:

Input:An undirected graph $ G$ and a positive integer $ K$ .

Goal:Does $ G$ have a clique of size at least $ K$ ?

Our problem:

Input:An undirected graph $ G$ and a positive integer $ K$ .

Goal:Is there a group of size $ K$ of super connectors in $ G$ ?

A *super connector* is a node with at least $ C$ (i.e., a fixed number of) edges. A group $ S$ of super connectors is a set of super connectors all connected to each other.

A group of super connectors is thereby a clique and a return value of TRUE from our problem will result in TRUE in the CLIQUE problem as well.

My idea to solve this is that I modify the graph by removing all nodes that aren’t super connectors. We are then left with a graph where every node is super connectors and can then input the graph in the CLIQUE problem to see if there exists a clique and thereby get a solution for our problem. By modifying the graph like this both of the problems will give the same outputs with the same inputs. Am I on the right path or completely wrong?