Questions tagged [independent-sets]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
1 answer

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?
maliya's user avatar
  • 11
1 vote
1 answer

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'...
Michal Dvořák's user avatar
1 vote
1 answer

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$. ...
Daniel Schwegler's user avatar
3 votes
1 answer

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? ...
wamengti's user avatar
0 votes
1 answer

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 ...
Soha's user avatar
  • 25
1 vote
1 answer

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 ...
ConScience's user avatar
1 vote
1 answer

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 ...
nicetyartwork's user avatar