Questions tagged [clique]

A clique is a subset of the vertices of a graph such that every pair of vertices in the subset is connected by an edge.

Filter by
Sorted by
Tagged with
3
votes
0answers
46 views

Number of maximal cliques in a graph where the largest induced cycle is $C_4$

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general, it is exponential. I am trying to determine whether the number ...
2
votes
0answers
28 views

Question about the lower bound for $k \times k$-clique (under ETH) shown in “Slightly Superexponential Parameterized Problems”

I am reading the paper Slightly Superexponential Parameterized Problems at the moment and have two questions about it: First question: The paper gives a proof of the following statement Theorem ...
2
votes
1answer
37 views

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 (...
2
votes
1answer
26 views

Algorithm to compute partitions of a graph in N cliques

does anyone know of an efficient algorithm to compute the partition of a graph in N cliques? Notice that N is the number of the cliques and not the size of them. I have heard of the 2 cliques ...
0
votes
1answer
99 views

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 ...
3
votes
0answers
177 views

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 ...
1
vote
1answer
44 views

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$. ...
2
votes
1answer
59 views

Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
5
votes
1answer
166 views

Prove that “Finishing the degree in three years” problem is NP-Complete

I was asked in an interview the following question: We'll define the "Finishing the degree in three years" problem in the following manner: Given a list of courses $C=\{c_1, c_2,\ldots, c_n\}$, ...
1
vote
2answers
61 views

Maximal cliques in a multipartite graph - efficient?

I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class. Now I am looking for the optimal subset such that each of the N classes is represented ...
4
votes
1answer
116 views

Does the intersection of VC and CLIQUE belong to NPC?

Define: $$L=\{(G,k) : G\text{ has a vertex cover of size at most $k$, and a clique of size at least $k$}\}$$ I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that $L\...
1
vote
1answer
425 views

Generalization of Subgraph Isomorphism

I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link ...
0
votes
0answers
56 views

Clique number of a graph given its order and average degree

Let $G$ be simple graph of order $N$, and let $\bar{d}$ be its average degree. Find the maximum value of $\omega(G)$ (the clique number of $G$) as a function of $N$ and $\bar{d}$. Find the ...
4
votes
1answer
113 views

Why is EXACT-CLIQUE not in co-NP?

In my lecture I saw the problem of $\text{EXACT-CLIQUE} = \{\langle G,k\rangle : \text{the largest clique in $G$ is of order $k$}\}$ I understand this problem is obviously not in NP as we would need ...
1
vote
0answers
34 views

Best-known Boolean Circuits for Clique? [closed]

Not having received a satisfactory response to this question in math.SE, I am asking it here: In this question, it is mentioned that the best known Boolean circuits for the Clique problem are non-...
3
votes
1answer
533 views

Given a set of intervals on the real line, find a minimum set of points that “cover” all the intervals

I've been trying to find an efficient way to solve the problem of finding a minimum (not minimal) set of time points that cover a given family of intervals on the real line, that is, for each interval ...
2
votes
1answer
55 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
2
votes
1answer
119 views

Understanding CLIQUE structure

I am working on the following problem: Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex is connected to every other vertex. Recall also that a clique is ...
2
votes
0answers
69 views

Finding maximum weighted n disjoint cliques

Maximum weight clique problem has some attention but i could not find any efficient approaches to this problem yet. I acknowledge that it is np-hard, but are there any known approximations? Given a ...
0
votes
1answer
254 views

Proving Clique Number of a Regular Graph

I am very new to Graph Theory and I am trying to prove the following statement from a problem set for my class: Prove that if G is a regular graph on n vertices $(n \ge 2)$, then $\omega(G) \in \{...
2
votes
1answer
118 views

An exact solution for biclique vertex-cover problem on a bipartite graph

The biclique vertex-cover problem asks whether the vertex-set of the given graph can be covered with at most "k" bicliques (complete bipartite subgraphs). It has been shown that "Biclique Vertex-...
1
vote
0answers
46 views

Finding minimum number of bicliques that cover nodes on one side of a bipartite graph

Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', ...
2
votes
1answer
109 views

Finding bicliques in a bipartite graph of minimum size

Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', ...
1
vote
2answers
72 views

Minimum number of vertices whose removal makes the graph an independent set

It is known that finding an independent set (or a clique) of size at least $k$ in a graph is $W[1]$ hard, so it is unlikely that there is $f(k)\cdot n^{O(1)}$ time algorithm for finding an independent ...
0
votes
1answer
73 views

Finding maximum clique in a distance matrix created by certain pattern

I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum ...
1
vote
2answers
266 views

Does the k-clique problem became easier on sparse graphs?

Some definitions, just to not create confusion: A sparse graph is a graph that contains a number of edges less or equal than the number of vertices. In $k$-clique problem we are given a graph and an ...
2
votes
1answer
360 views

Probability of k-clique in a random graph

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random ...
0
votes
0answers
61 views

Listing all maximal cliques with mean edge weight at least k in a weighted complete graph

Given a weighted undirected complete graph G = (V,E). I am interested in finding all maximal cliques that have mean edge weight (mean of weights of all edges in the clique) at least k. Most of the ...
0
votes
1answer
57 views

Hueristic Algorithm to find the maximum clique

Let the algorithm be defined as follows: Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every ...
1
vote
1answer
136 views

What is the exact algorithm to find maximum clique of a given unit disk graph?

A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ ...
2
votes
2answers
179 views

Is $k$-CLIQUE W[1]-hard for parameter $n - k$?

It is well-known that the problem of deciding if a graph contains a clique of size $k$ is W[1]-hard with respect to parameter $k$. Is it also known to W[1]-hard (or perhaps FPT) in parameter $n - k$, ...
3
votes
1answer
537 views

Algorithm for finding cliques

Given an arbitrary undirected graph $G = (V,E)$, I am interested in a low-polynomial time algorithm which can find several moderately large (ideally $O(n^\epsilon)$ vertices per clique for $\epsilon &...
2
votes
2answers
75 views

What is the relationship between minimum sized vertex covers and complete graphs?

What is the relationship between the sizes of minimum sized vertex covers and complete graphs?
5
votes
1answer
170 views

Is there a reasonable algorithm to generate a certain “independent clique graph” with minimal vertices?

In the process of trying to find a solution to the rat and poison puzzle with two rats, I've found myself needing the solve the following problem, in polynomial time: Given any $k_0, k_1, k_2,..., k_{...
1
vote
1answer
614 views

reducing $CLIQUE$ from decision to search problem

consider the language:$$CLIQUE = \left\{\langle G,k\rangle \ |\ \text{ $G$ is a graph containing a clique of size at least $k$ } \right\}$$ Suppose there's a polynomial time algorithm for $CLIQUE$. ...
-1
votes
1answer
60 views

Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

Recall the notion of NPO problem. An NPO problem is simple if the following is true: $\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$ In words, given any positive integer $k$, the ...
1
vote
1answer
82 views

Reduction from Clique to something else

Given $G(V,E)$ and $k$. Is there a clique with size $k$? Given set $X = \{x_1,x_2,\dots,x_n \}$, and collection $A = \{A_1,A_2,...,A_n\}$ of sub-sets of $X$ and $k$. Are there are $k$ different ...
0
votes
1answer
302 views

Number of cliques in a graph

I think the number of cliques in a graph is generally exponential in the of vertices of that graph. Does anyone know any reference for that?
2
votes
1answer
558 views

Reduction from Clique-6 to Clique-3

Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Let us define the problem $Clique-k$ as follows: $$\{ \langle G \rangle \mid G \text{ is an ...
1
vote
2answers
656 views

Prove “almost clique” is NP complete

Given $G=(V,E)$, undirected graph, a group of vertices $S$ is called almost clique if by adding a single edge, $S$ becomes a clique. Consider the language: $L=\{\langle G,t\rangle \mid \text{the ...
0
votes
1answer
136 views

Colored cliques complexity

Given: graph with colored edges; list of $\alpha$ colors; list of $\epsilon$ colors; clique size $k$. Problem: Do all edges colored in one of $\alpha$ colors are members of cliques with size $k$? ...
0
votes
1answer
265 views

Reduce Clique to Set Cover

Is it possible directly to reduce clique to set cover? I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to ...
4
votes
1answer
919 views

What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?

Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from wikipedia): ...
2
votes
1answer
42 views

Algorithm to get maximal selection set of a collection of sets with a binary relation

I have a finite collection of finite sets $\{A_i\}_{i \in I}$. There is a relation $R$ defined on the elements of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose ...
7
votes
1answer
6k views

Having trouble in understanding the definition of a clique

My definition says A clique is a graph that has an edge connecting every pair of vertices but as I understand, an edge connects only two vertices. Like $A-B$. If we want to connect three vertices,...
0
votes
2answers
728 views

How to prove 3CLIQUE is decidable

From our computational complexity, there's a question asking to prove 3CLIQUE is decidable. The definition of 3CLIQUE is: $$\{(V,E) : G = (V,E)\text{ is an undirected graph that contains a clique of ...
2
votes
1answer
56 views

Minimum number of sets of points

During my work I've encountered this problem: $G = \{(x_i,y_i,z_i)\}_{i=1}^{n}$ is a group of points in space ($\forall i \;\; x_i,y_i,z_i \in \Bbb R$) and $ d \in \Bbb R^+$ is a constant. Divide $...
-1
votes
1answer
130 views

Maximum # of nodes with maximum 3-distance in ternary tree

how is it possible to calculate this kind of problem that asks to find the maximum amount of nodes in ternary tree where the maximum distance from a node to another node is 3? if the maximum distance ...
1
vote
0answers
99 views

NP-hardness of finding almost cliques

Here's a problem that came up when organizing a party: You need to place $n$ guests in tables of size 10. Each guest has a list of $m$ other guests they'd like to have in their table. Find a seating ...
5
votes
1answer
419 views

Reduce $\sqrt{n}$-CLIQUE to CLIQUE

Recall that $G$ has a clique of size $k$ if it has a complete sub graph consisting of $k$ vertices. Define CLIQUE as the decision problem $$\{ \langle G, c \rangle \mid G \text{ has a clique of size }...