Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

The tag has no usage guidance.

2
votes
0answers
141 views

A variant of the Maximum Weight Clique problem

I am trying to solve a problem that I could reduce to the following: Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
1
vote
0answers
139 views

Reduction from k-Almost Independent Set to Independent Set

The problem of $k$-Almost Independent Set is to decide whether or not $(G,m)$ where $G$ is a graph and $m \in \mathbb{N}$ has a subset of $m$ vertices that induces a subgraph with at most $k$ edges. I ...
1
vote
1answer
127 views

Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known

Given a $k>0$ and a graph $G(V,E)$ with known independence number $\sqrt{|V|}\leq\alpha(G)\leq\alpha\sqrt{|V|}$ and chromatic number $\frac1\beta\sqrt{|V|}\leq\chi(G)\leq\sqrt{|V|}$ for some fixed $...
1
vote
2answers
185 views

Reduction from independent set in hypergraphs to independent set in graphs

Let me introduce my notations. IS-H : Input : an hypergraph $G=(V,H)$, an integer $k$ Question : is there a (weak) independent set of size $k$, i.e. a set $S \subseteq V$ such that $|S| \ge k$ and ...
0
votes
1answer
187 views

Paritioning a graph into clique and independent set

I am interested in the complexity of the following problems: Input: an undirected graph $G = \langle V, E \rangle$ Query 1: is there a partition of $V$ into two a clique $C$ and an independent set $...
7
votes
2answers
721 views

SDP relaxation of independent set

I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph $$\max u' Z u$$ subject to $$Z\...