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

<p>Given $G=(V,E)$ and $k$ construct $G'$ with</p>

<ul>
<li>vertex set $V \times \{1,\dots,k\}$ and</li>
<li>edges between $(v,i)$ and $(w,j)$ if</li>
</ul>

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

<p>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$.</p>

CC BY-SA 3.0
2015-03-06T12:00:09.457Z
@András: Thank you for bringing this into a nice form. I have to learn how to use LaTeX markup around here.
Thomas S
CC BY-SA 3.0
2015-03-06T12:54:40.150Z
Most LaTeX "just works", even stuff like `\stackrel` and AMS extensions.
András Salamon
CC BY-SA 3.0
2015-02-27T21:53:39.953Z
2015-03-06T09:06:20.373Z
2015-03-06T09:06:20.373Z
Thomas S
<p>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:</p>

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

<p>where $MIS(G)$ collects all possible maximal independent sets of $G$.</p>

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

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

<p>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.</p>

<p>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}$.</p>

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

<p>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. </p>

CC BY-SA 4.0
2021-01-12T07:34:28.683Z
The other direction $M_{eq} \leq_m M_{ineq}$? is still open. Does anyone have any idea how to solve that?
gov
<cc.complexity-theory><graph-theory><graph-algorithms><reductions>
Many-one reduction from inequality problem to equality problem
Fredrik Savje
# Many-one reduction from inequality problem to equality problem

(Asked by: username_0 on 2015-02-24)

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.

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms, reductions

> **Comments:**
> **username_1**: The other direction $M_{eq} \leq_m M_{ineq}$? is still open. Does anyone have any idea how to solve that?  

---

## 1 answers

### Answer by username_2 on 2015-02-27. Score: 3 | Accepted answer

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$.

> **Comments:**
> **username_2**: @András: Thank you for bringing this into a nice form. I have to learn how to use LaTeX markup around here.  
> **username_3**: Most LaTeX "just works", even stuff like `\stackrel` and AMS extensions.  

---

