<p>It is NP-complete even when <span class="math-container">$G[B]$</span> 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, so MIS is NP-complete in twice subdivided graphs, but twice subdivided graphs can be partitioned into an independent set and a disjoint union of cliques of size 2.</p>

CC BY-SA 4.0
2023-06-16T19:16:23.410Z
2023-06-16T19:16:23.410Z
Laakeri
<p>No. A graph with <span class="math-container">$n$</span> vertices is trivially <span class="math-container">$(n, 1)$</span>-colorable. So solving MIS in <span class="math-container">$(p, 1)$</span>-colorable graphs in <span class="math-container">$n^{O(1)}$</span> time for non-constant <span class="math-container">$p$</span> implies we could solve MIS in <span class="math-container">$n^{O(1)}$</span> time for any graph.</p>

CC BY-SA 4.0
2023-06-16T17:11:51.873Z
Sorry, I found a wrong definition. It is not a $(p,1)$-colorable graph.
Blanco
CC BY-SA 4.0
2023-06-16T17:01:26.073Z
2023-06-16T17:01:26.073Z
sherp
<p>It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable.
What happens if we generalize the input graphs by replacing the vertices in one partite with cliques?</p>
<p>Formally, the graph <span class="math-container">$G = (V, E)$</span> is defined as follows.
There is partition <span class="math-container">$(A, B)$</span> of <span class="math-container">$V$</span> such that <span class="math-container">$G[A]$</span> is an independent set and <span class="math-container">$G[B]$</span> is a cluster (the union of some disjoint cliques).</p>
<p>I wonder whether whether MIS in such graph classes is polynomial-time solvable.</p>

<reference-request><np-hardness><polynomial-time><independent-set>
Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?
Blanco
# Is Maximum Independent Set polynomial-time solvable in $(p,1)$-colorable graphs for general $p$?

(Asked by: username_0 on 2023-06-16)

It is well-known that Maximum Independent Set (MIS) in bipartite graphs is polynomial-time solvable.
What happens if we generalize the input graphs by replacing the vertices in one partite with cliques?

Formally, the graph $G = (V, E)$ is defined as follows.
There is partition $(A, B)$ of $V$ such that $G[A]$ is an independent set and $G[B]$ is a cluster (the union of some disjoint cliques).

I wonder whether whether MIS in such graph classes is polynomial-time solvable.

**Tags:** reference-request, np-hardness, polynomial-time, independent-set


---

## 2 answers

### Answer by username_1 on 2023-06-16. Score: 3 | Accepted answer

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, so MIS is NP-complete in twice subdivided graphs, but twice subdivided graphs can be partitioned into an independent set and a disjoint union of cliques of size 2.


---

### Answer by username_2 on 2023-06-16. Score: 0

No. A graph with $n$ vertices is trivially $(n, 1)$-colorable. So solving MIS in $(p, 1)$-colorable graphs in $n^{O(1)}$ time for non-constant $p$ implies we could solve MIS in $n^{O(1)}$ time for any graph.

> **Comments:**
> **username_0**: Sorry, I found a wrong definition. It is not a $(p,1)$-colorable graph.  

---

