-1
$\begingroup$

Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\{u,v\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}_{>0}$ where $|I|=k$.

How can I define the language $L_{P_{Independent Set}}$ to this decision problem?

I know that $I$ could be written as $I = \{u,v\} \in V | \{(u,v)\}\notin E \}$ but don't really understand how to describe the language.

$\endgroup$
3
  • $\begingroup$ Let the size of independent set i.e. $k$ range over all positive integers with an additional constraint that $k$ is smaller than the number of vertices in the graph being considered. $\endgroup$ Jul 12, 2017 at 11:40
  • $\begingroup$ Duplicate of determine the language of the independent set problem. $\endgroup$
    – Pål GD
    Jul 12, 2017 at 19:28
  • 1
    $\begingroup$ What is $P_{IndependentSet}$? Please define this problem formally then you may find the answer yourself. $\endgroup$
    – xskxzr
    Apr 9, 2018 at 6:02

1 Answer 1

1
$\begingroup$

A language $L$ describes decision problem $p$ means that $\forall x \in L $ the instance $x$ is a Yes/Accept instance of $p$.

For the independent set problem, we have to define language $L$ such that every $x\in L$ is an independent set of graph $G=(V, E)$.

So one possible way to define decision language for independent set problem is $$\begin{array}{ll} L & = \{I \mbox{ such that } I\subseteq V \mbox{ and }\forall u,v\in I,\;\; (u,v)\notin E\} \\ & = \{I \;\;|\;\; I\subseteq V \mbox{ and }\forall u,v\in I, \;\; (u,v)\notin E\} \end{array} .$$

If you wish to define the language generally you can write it as $$ \begin{array}{ll} L & =\{(G=(V,E),I) \mbox{ such that } I\subseteq V \mbox{ and }\forall u,v\in I,\;\; (u,v)\notin E\}\\ & =\{(G=(V,E),I) \;\;|\;\; I\subseteq V \mbox{ and }\forall u,v\in I,\;\; (u,v)\notin E\} \end{array} .$$

$\endgroup$

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.