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
1answer
42 views

On Tarjan's paper “Finding a Maximum Clique”

In his paper, "Finding a Maximum Clique" from 1972 Robert Tarjan introduced an algorithm that finds maximum cliques in $O(1.286^n)$. You can find a link to his paper here. In the second page ...
0
votes
1answer
27 views

What is the complexity of k-clique problem with a predetermined vertex in the solution?

Clique (from WikiPedia): Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. K-Clique ...
1
vote
0answers
17 views

ILP relaxation for Cluster deletion on C5

I'm looking for additional constraints that get rid of fractional solutions for the LP relaxation of the Cluster Deletion problem: Given an undirected graph $G = (V, E)$, find a min. sized $E' \...
0
votes
1answer
94 views

Solving distance-d independent set in a simple way

I'm solving distance-d independent set problem, as a follow up to my last question. I'm not quite experienced in a subject, so I'm looking for a simple algorithm (which has to be an exact algorithm). ...
1
vote
2answers
63 views

Is $\frac{n}{3}$-CLIQUE NP-complete?

Consider the problem $\frac{n}{3}$-CLIQUE: determining whether a graph contains a clique with at least $n/3$ vertices. I want to prove it is NP-complete using a polynomial transformation from CLIQUE. ...
1
vote
2answers
175 views

Max clique in interval graph

According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. ...
1
vote
2answers
146 views

Clique-problem for planar graph

I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion This follows already from Kuratowski's theorem: a clique is at ...
2
votes
1answer
57 views

Minimum unweighted anticlique (independent set) cover / partition

Suppose I have a set of integer intervals, and I want to generate a visualization like the one attached. One obvious way of accomplishing this is to put every interval in its own row; this obviously ...
7
votes
1answer
191 views

Number of maximal cliques in a ($2C_4$, $C_5$, $P_5$)-free graph [closed]

So far, I have found out that chordal graphs have linear number of maximal cliques with respect to the number of vertices. In general case, it is exponential. I am trying to determine whether the ...
2
votes
0answers
33 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
97 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
30 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
184 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
469 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
55 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$. Goal: Does $...
2
votes
1answer
62 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
175 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
101 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 exactly ...
4
votes
1answer
129 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
572 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
67 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
226 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
35 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
1k 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
65 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
314 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
76 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 ...
1
vote
1answer
400 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
154 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
47 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
114 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
95 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
95 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
431 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
459 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
72 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
67 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
192 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
234 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
592 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
157 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?
6
votes
1answer
222 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
2answers
798 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
72 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
228 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
645 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
723 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
925 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
157 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
301 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 ...