# Tag Info

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
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 ...
• 51.1k

### 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
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\}$. ...
• 136
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,786

### 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
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,786
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 ...
• 10.8k
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) ...

### 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 ...
• 17.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 ...
• 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.
• 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 ...
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$ ...

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