Many-one reduction from inequality problem to equality problem

Question

Let the k-inequality-MIS problem be the decision problem whether an arbitrary graph $G=(V, E)$ contains a maximal independent set of at least size $k$, that is the corresponding language is:

$$\mathbf{M}_{ineq} = \{(G,k): \exists V'\subset V, |V'|\geq k \wedge V'\in MIS(G)\},$$

where $MIS(G)$ collects all possible maximal independent sets of $G$.

Let the k-equality-MIS problem be the decision problem whether $G$ contains such a set exactly of size $k$. Its language being:

$$\mathbf{M}_{eq} = \{(G,k): \exists V'\subset V, |V'|=k \wedge V'\in MIS(G) \}$$

I'm wondering whether $\mathbf{M}_{eq}$ is many-one reducible to $\mathbf{M}_{ineq}$. My intuition tells me it should be but I cannot get it working. As I suspect similar problems pop up quite often, I figured someone here might know.

Note that this is not trivial as the corresponding independent sets problem, $\mathbf{I}$, where $(G,k)\in\mathbf{I}_{ineq}\Leftrightarrow (G,k)\in\mathbf{I}_{eq}$. As an example, for a graph, $G'$, that is a perfect matching with more than two vertices we have $(G',1)\in\mathbf{M}_{ineq}$ but $(G',1)\not\in\mathbf{M}_{eq}$.

And how about the other way around, is $\mathbf{M}_{ineq}$ many-one reducible to $\mathbf{M}_{eq}$?

I'm quite new to complexity theory, so I hope I get this right and the question is not obvious. Also sorry for the rather vague title, but my question is a bit vague. I hope my example made it clear. My question is, however, really about all problems with similar characteristics.

Answer 1

The following should yield a many-one reduction from $M_{ineq}$ to $M_{eq}$:

Given $G=(V,E)$ and $k$ construct $G'$ with

• vertex set $V \times \{1,\dots,k\}$ and
• edges between $(v,i)$ and $(w,j)$ if

(1) $i=j$ or (2) $v=w$ or (3) $(v,w) \in E$.

Because of (1), no independent set can be larger than $k$ (as all vertices in the same slice are connected). Because of (2) and (3) each independent set in $G'$ induces an independent set of $G$ and vice versa, therefore $G$ has an ind. set of size $\ge k$ if and only if $G'$ has an independent set of size exactly $k$.