On independent domination in direct products

NEW

Problem: For finite simple graphs, let $G\times H$ be the direct product and let $i(X)$ be the minimum size of a maximal independent set of $X$. The reconstructed decision problem is:

Input: a graph $G$, an integer $n\ge 3$, and an integer $k$.
Question: is $i(G\times K_n)\le k$?

This is exactly the boxed problem stated in the source paper.

Result: The problem is NP-complete, even when $n=3$ is fixed and $G$ is bipartite.

Membership in NP follows from the standard layer characterization for $G\times K_n$, $n\ge3$: every layer over $v\in V(G)$ contributes either $0$, $1$, or $n$ vertices to a maximal independent set, so a certificate is a labeling of each $v$ by $0$, one color in $[n]$, or $[n]$, verifiable in polynomial time.

For NP-hardness, reduce from 3-COLORABILITY. Given a graph $Q$ with vertices $v$, construct $G$ as follows. For each $v\in V(Q)$, add an edge $a_vb_v$. For each edge $uv\in E(Q)$, add a vertex $z_{uv}$ adjacent exactly to $a_u$ and $a_v$. Let $n=3$ and $k=2|V(Q)|$. The graph $G$ is bipartite.

If $Q$ has a proper 3-coloring $c$, label both $a_v,b_v$ with singleton color $c(v)$, and label every $z_{uv}$ by $0$. This has weight $2|V(Q)|$, each singleton-labeled vertex has a same-colored neighbor, and each zero-labeled $z_{uv}$ sees two distinct colors, so it yields an independent dominating set of $G\times K_3$.

Conversely, suppose $i(G\times K_3)\le 2|V(Q)|$. For each pendant vertex $b_v$, its layer-label forces the pair $\{a_v,b_v\}$ to contribute at least $2$: if $b_v$ is zero, then its only neighbor $a_v$ must be full, contributing $3$; if $b_v$ is full, it contributes $3$; if $b_v$ has singleton color $j$, then $a_v$ must also have color $j$. Hence all pairs contribute exactly $2$, every $z_{uv}$ contributes $0$, and each $a_v,b_v$ has a common singleton color $c(v)$. Since $z_{uv}$ is zero and has only neighbors $a_u,a_v$, domination requires $c(u)\ne c(v)$. Thus $c$ is a proper 3-coloring of $Q$.

Therefore the decision problem is NP-hard and, since it lies in NP, NP-complete.

Audit: no extra hypotheses beyond finite simple graphs and $n\ge3$ were used; the reduction fixes $n=3$, so it proves the stated variable-$n$ problem hard as well.

Citation: The problem statement is from Kuenzel and Rall, “On independent domination in direct products,” arXiv:2203.12397. The reduction uses the standard NP-completeness of 3-COLORABILITY, e.g. Garey, Johnson, and Stockmeyer, Theoretical Computer Science 1 (1976), 237–267.