Questions tagged [independent-sets]
The independent-sets tag has no usage guidance.
7
questions
1
vote
1
answer
29
views
Independent sets generation in a graph
Is there an algorithm that, given an undirected graph and one independent set IS1, finds an other independent set IS2 by adding and deleting vertices from the first IS1?
- 11
1
vote
1
answer
46
views
How to express that a graph has Independent set of size at least $n/2$ in $\exists SO$
I am looking to provide a formula saying "A graph with $n$ vertices has an independent set $X$ of size at least $n/2$" in existentional second order logic.
(This is exercise 1.2. from Libkin'...
- 267
1
vote
1
answer
38
views
Densest Sub Graph and forbidden Pairs
Given two graphs $G$ and $F$ on the same vertex set $V$. Compute a sub set $\tilde{V}\subset V$ which' sub graph of $G$ is of maximum density and does not have any pair that is connected in $F$.
...
3
votes
1
answer
340
views
Maximum Independent Set of a Tree using Greedy Algorithm
I was attempting to solve "Maximum Independent Set of a Tree" and came up with an algorithm that resembled this one Why is greedy algorithm not finding maximum independent set of a graph?
...
- 31
0
votes
1
answer
190
views
Is maximal independent set on maximal planar graphs still NP-complete?
We know that finding the size of the maximal independent set of a planar graph is NP-complete. I'm curious about whether it remains NP-complete for maximal planar graphs, i.e., the graphs in which ...
- 25
1
vote
1
answer
162
views
Prove the expected size of the independence set got by a random algorithm is at least 1/d of the maximum size
I am doing an exercise related to maximizing Independent Set, I have $G = (V = \{v_1, . . . , v_n\}, E)$ as an undirected graph. This graph as $n!$ possible orderings for the vertices $V$.
If we pick ...
- 25
1
vote
1
answer
312
views
Why is Independent Set "at least" and Vertex Cover "at most" k
The decision version of the Independent Set and Vertex Cover problems are phrased as:
Given a graph G and a number k, does G contain an independent set of size at least k?
Given a graph G and a ...
- 113