Consider the following two problems on undirected graphs:
α: Given G(V,E), does G have an independent set of size |v|—4?
β: Given G(V,E), does G have an independent set of size 5?
Which one of the following is TRUE?

Related MCQs

• Consider the following decision problems: (P1) Does a given finite state machine accept a given string (P2) Does a given context free grammar generate an infinite number of stings Which of the following statements is true?
• Consider the following grammar. S -> S * E S -> E E -> F + E E -> F F -> id Consider the following LR(0) items corresponding to the grammar above. (i) S -> S * .E (ii) E -> F. + E (iii) E -> F + .E Given the items above, which two of them will appear in the same set in the canonical sets-of-items for the grammar?
• Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
• Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
• Consider the following two statements: P: Every regular grammar is LL(1) Q: Every regular set has a LR(1) grammar Which of the following is TRUE?
• Consider the following two sets of LR(1) items of an LR(1) grammar. X -> c.X, c/d X -> .cX, c/d X -> .d, c/d X -> c.X, $ X -> .cX, $ X -> .d, $ Which of the following statements related to merging of the two sets in the corresponding LALR parser is/are FALSE? 1. Cannot be merged since look aheads are different. 2. Can be merged but will result in S-R conflict. 3. Can be merged but will result in R-R conflict. 4. Cannot be merged since goto on c will lead to two different sets.
• Consider the grammar defined by the following production rules, with two operators ∗ and + S --> T * P T --> U | T * U P --> Q + P | Q Q --> Id U --> Id Which one of the following is TRUE?
• Consider the following expression grammar. The seman-tic rules for expression calculation are stated next to each grammar production. E → number E.val = number. val | E '+' E E(1).val = E(2).val + E(3).val | E '×' E E(1).val = E(2).val × E(3).val The above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yacc for the given grammar?
• Consider the language L1,L2,L3 as given below. L1={0^{p}1^{q} | p,q \in N} L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r} Which of the following statements is NOT TRUE?
• Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are