1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The other direction $M_{eq} \leq_m M_{ineq}$? is still open. Does anyone have any idea how to solve that? $\endgroup$
    – gov
    Jan 12, 2021 at 7:34

1 Answer 1

3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @András: Thank you for bringing this into a nice form. I have to learn how to use LaTeX markup around here. $\endgroup$
    – Thomas S
    Mar 6, 2015 at 12:00
  • $\begingroup$ Most LaTeX "just works", even stuff like \stackrel and AMS extensions. $\endgroup$ Mar 6, 2015 at 12:54

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.