10
votes
Accepted
Is the maximum independent set in cubic planar graphs NP-complete?
A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.
Bojan Mohar:
"Face Covers and the Genus Problem for Apex Graphs"
Journal of ...
- 5,772
6
votes
Accepted
Paritioning a graph into clique and independent set
Question (1) is easy polynomial time. As Juho has already mentioned in comments, the graphs that can be partitioned into a clique and an independent set are the split graphs. They can be recognized ...
- 50.9k
5
votes
Deciding $\omega(G)>k$ when $\alpha(G)$ and $\chi(G)$ have bounds and are known
The NP-hardness proof for CLIQUE in the book by Garey and Johnson shows that the following problem is NP-complete:
Instance: An integer $k$; a $k$-partite graph $G=(V,E)$
Question: Does $G$ ...
- 5,772
4
votes
Accepted
Independent set queries with preprocessing
If the graph is uniformly sparse in the sense that every subgraph with $n$ vertices contains at most $d \cdot n$ edges for some small $d$, then degeneracy ordering could be exploited to have $O(|E|)$ ...
- 1,767
3
votes
Reduction from independent set in hypergraphs to independent set in graphs
From the standard machinery, we can quickly deduce that there is a quasilinear-time reduction from $\textrm{IS-H}$ to $\textrm{IS}$. (But see below if quasilinear isn't good enough for you.)
Recall ...
- 1,429
3
votes
Accepted
Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?
It is NP-complete even when $G[B]$ is a disjoint union of cliques of size 2. This follows from the fact that subdiving every edge twice increases maximum independent set by exactly the number of edges,...
- 1,767
3
votes
Accepted
Hardness of Maximum Independent Set in 3-Colorable Graphs
As detailed below, the problem of finding an independent set of size $\Omega(n^{1-\delta})$ in 3-colorable graphs is essentially equivalent to $O(n^\delta)$-approximating 3-COLOR. Currently, the best ...
- 9,595
3
votes
Accepted
Approximation algorithm for balanced bipartite independent set?
There is a nice reduction by Chalermsook et al. (WG 2020) that can give the kind of approximation you want. I'll describe it below in terms of finding balanced complete bipartite subgraph (biclique) ...
- 306
2
votes
Proof that optimal solutions of LP Relaxation of independent set are half-integral
The LP in question is a maximization over a bounded polytope, hence the optimal value is attained at a vertex of the polytope. Moreover, any vertex can be described as a unique solution of a system of ...
- 16.9k
1
vote
Proof that optimal solutions of LP Relaxation of independent set are half-integral
This is discussed in a related cstheory post:
LP relaxation of independent set
That post cites this publication:
[1] Nemhauser, G.L., Trotter, L.E. Vertex packings: Structural properties and ...
- 9,595
1
vote
Is the maximum independent set in cubic planar graphs NP-complete?
Actually, there is a simple gadget to remove vertices of degree larger than three. See, e.g., the answer here. Note that this gadget keeps planarity.
- 2,560
1
vote
Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$
I don't think the Bollobás paper asserts the bound on the independence number; rather, it seems to me that it asserts that for any given maximum degree $\Delta$ and lower bound on the girth $g$, there ...
- 800
1
vote
Reduction from independent set in hypergraphs to independent set in graphs
I am not as convinced as @Andrew Morgan is that this is "fair standard fare", and would also welcome pointers to a citable reduction.
In particular, I do not see how to maintain a linear blowup if $k$ ...
- 18.9k
Only top scored, non community-wiki answers of a minimum length are eligible