1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Sorry, I found a wrong definition. It is not a $(p,1)$-colorable graph. $\endgroup$
    – Blanco
    Jun 16, 2023 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.