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
7
votes
1answer
9k 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
866 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
60 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
149 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
100 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
835 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 }...
1
vote
2answers
264 views

Parameterized vertex cover on $r$-regular graphs

I am trying to solve the following exercise from this book: Show that CLIQUE PROBLEM, parameterized by the solution size $k$, is Fixed-parameter tractable (FTP) on $r$-regular graphs for every ...
3
votes
1answer
408 views

Why doesn't greedy work for Clique?

In reference to this problem (equivalently, findind a maximal clique in an undirected graph), I believe greedy approach should work (i.e. removal of people who have maximal qualms with others.). ...
2
votes
1answer
3k views

Why is Clique NP-complete while k-Clique is in P for all k?

I just stumbled upon this question here Why is the clique problem NP-complete? and I am confused by the given answer. The question about about whether $k$-clique is NP-hard for a fixed $k$ and the ...
3
votes
1answer
268 views

Implementing Nesetril and Poljak's clique detection algorithm

I want to implement the clique detection algorithm by Nesetril and Poljak described in [1]. However, I can't seem to understand how the auxiliary graph $H$ is to be created and how it can be used to ...
0
votes
1answer
1k views

If the Clique-k Problem is in P, why not Clique as well?

I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?) The general clique problem is defined as $\text{CLIQUE} = \left\{ (G, k) | ...
0
votes
2answers
1k views

Showing that 3-colorable is NP-complete

Just as a background, 3-colorable problem is as follows: Given a graph $G = (V, E)$, is it possible to color the vertices using just 3 colors such that no neighboring vertices have the same color? I'...
4
votes
2answers
931 views

Expected number of independent sets of size $k$ in random graph $G(n,p)$

I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is ...
4
votes
1answer
1k views

Showing a problem is NP complete? Reducing CLIQUE to KITE.

I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc. The problem is, there doesn't ...
0
votes
0answers
164 views

k clique edit is FPT

I am doing a problem on fixed parameter tractability where in we are given a graph G=(V,E), and an integer k, and the k-clique edit problem asks whether there exists a set U i.e a subset of V such ...
3
votes
1answer
195 views

Why is bipartite perfect matching a special case of clique problem?

In Lovász writes [1] : bipartite graph has a perfect matching, which is a special case of the clique problem Why is bipartite perfect matching a special case of clique problem? The Work of A.A. ...
1
vote
1answer
93 views

NP-complete reduction for a k-dumbbell graph

A k-dumbbell is a graph that consists of 2 cliques each of size k with one and only one edge between them. How do I show that finding if a graph is a k-dumbbell is NP-complete? Proof it is in NP: ...
6
votes
1answer
324 views

Modified Clique Problem

We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two ...
4
votes
1answer
141 views

Hardness of a special GAP-CLIQUE problem

In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be ...
0
votes
1answer
226 views

pseudo clique with at least connectivity x and maximum weight of the nodes

Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = \sum_{...
1
vote
1answer
437 views

Can I find a clique with more than 2 nodes in a bipartite graph?

As in the title, is it possible to find a clique with more than 2 nodes in a bipartite graph?
2
votes
2answers
2k views

Covering a graph with non-overlapping cliques

I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows: Every subgraph must be a complete graph/clique No vertex can be part of two or more ...
-1
votes
1answer
346 views

NDTM for Graph Clique Problem in poly-time

I am having a doubt. This is my NDTM algorithm: GCP(G, k): generate a list with k distinct nodes from graph G generate an adjacency matrix, fill it with 1 if an edge exist, 0 otherwise check if ...
1
vote
2answers
3k views

Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this: What is the minimum size of the largest clique in any graph with N ...
0
votes
1answer
628 views

Finding vertices of a maximum clique in polynomial time [duplicate]

Say you were given a black box that solves a clique problem in constant time. You give the black box an undirected graph G with a bound k and it outputs either "Yes" or "No" that the graph G has a ...
10
votes
2answers
1k views

The equivalence relations cover problem (in graph theory)

An equivalence relation on a finite vertex set can be represented by an undirected graph that is a disjoint union of cliques. The vertex set represents the elements and an edge represents that two ...
6
votes
1answer
481 views

Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...

1
2