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.

11 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
1answer
175 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_{...
3
votes
0answers
47 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 ...
3
votes
0answers
213 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 ...
2
votes
0answers
30 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
0answers
72 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
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', ...
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 ...
0
votes
0answers
58 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 ...
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
0answers
159 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 ...
-1
votes
1answer
133 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 ...