# Questions tagged [independent-sets]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
26 views

### Optimizing Set Composition with String Edit Distance Constraints

A set $S$ consisting of strings of length $L$ using $N$ types of characters is such that the edit distance between any two strings is at least $d$. Among such sets $S$, I would like to find one with ...
60 views

### Find an independent set in which the cumulative sum of weights is maximized

I have a weighted undirected graph G=(V,E,W), I want to find an independent set S of V, such ...
• 385
74 views

### Minimum number of edges required to limit the size of the independent set

Consider the following problem: For $k \le n$, what is the smallest number of edges in the graph with $n$ vertices so that the maximum independent set has size at most $k$? I.e., given an empty ...
• 345
28 views

### How can I model this optimization problem?

We're looking to model the following problem as a standard optimization problem (or even a non-standard one). We can come close, but nothing seems to fit exactly. We have a working algorithm coded, ...
• 133
1 vote
31 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
63 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'...
1 vote
39 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$. ...
662 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
282 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
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 ...