Skip to main content
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 ...
Gamow's user avatar
  • 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 ...
David Eppstein's user avatar
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$ ...
Gamow's user avatar
  • 5,772
4 votes
Accepted

Tree decompositions with unique witness for each edge

I'm afraid the answer to both of your questions is no. Consider a graph $(V_n, E_n)$ with $V_n = \{1,...,n+2\}$ and $E = \{\{i,i+1\} | 1 \leq i \leq n+1\} \cup \{\{i,i+2\} \mid 1 \leq i \leq n\}$. ...
Corto's user avatar
  • 136
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|)$ ...
Laakeri's user avatar
  • 1,786
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 ...
Andrew Morgan's user avatar
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,...
Laakeri's user avatar
  • 1,786
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 ...
Neal Young's user avatar
  • 10.8k
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) ...
Pasin Manurangsi's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Neal Young's user avatar
  • 10.8k
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.
Yixin Cao's user avatar
  • 2,559
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 ...
Jason Gaitonde's user avatar
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$ ...
András Salamon's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible