Skip to main content

Questions tagged [independent-sets]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
Kazune Takahashi's user avatar
0 votes
0 answers
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 ...
Farah Mind's user avatar
3 votes
0 answers
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 ...
Dmitry's user avatar
  • 345
3 votes
1 answer
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, ...
Ted Hopp's user avatar
  • 133
1 vote
1 answer
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?
maliya's user avatar
  • 11
2 votes
1 answer
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'...
Michal Dvořák's user avatar
1 vote
1 answer
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$. ...
Daniel Schwegler's user avatar
3 votes
1 answer
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? ...
wamengti's user avatar
0 votes
1 answer
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 ...
Soha's user avatar
  • 25
1 vote
1 answer
210 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 ...
ConScience's user avatar
2 votes
1 answer
437 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 ...
nicetyartwork's user avatar