Question

Exercise 1 (1 point for each correct answer) For each of the following statements indicate whether...

Exercise 1 (1 point for each correct answer) For each of the following statements indicate whether it is true, false, or unknown.

1. The MIN VERTEX COVER problem is in ??.

2. The MIN VERTEX COVER problem is ??-hard.

3. The MIN VERTEX COVER problem can be solved by a 3-approximation algorithm.

4. The MIN VERTEX COVER problem can be solved by a 1-approximation algorithm.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

1. The MIN VERTEX COVER problem is in ??. FALSE
Explanation: MIN VERTEX COVER problem is  optimization problem of finding a minimal(least) vertex cover in the provided graph. MIN VERTEX COVER problem is NP-complete

2. The MIN VERTEX COVER problem is ??-hard. FALSE
explanation: MIN VERTEX COVER problem is  optimization problem of finding a minimal(least) vertex cover in the provided graph. MIN VERTEX COVER problem is NP-complete . where NP-hard is not a decision problem , NP-complete is exclusively a decision problem.

3. The MIN VERTEX COVER problem can be solved by a 3-approximation algorithm. FALSE

4. The MIN VERTEX COVER problem can be solved by a 1-approximation algorithm. TRUE
Explanation: We can solve it in exactly polynomial time

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
For each of the following statements indicate whether it is true, false, or unknown. The SAT...
For each of the following statements indicate whether it is true, false, or unknown. The SAT problem is in P. The SAT problem is in NP. The SAT problem is in EXP.
Indicate whether each of the following statements is True or False, and Briefly Justify your answer....
Indicate whether each of the following statements is True or False, and Briefly Justify your answer. The adjusted R2 is used because the unadjusted R2 automatically and spuriously increases when extra explanatory variables are added to the model.
1. In this problem, the domain of x is integers. For each of the statements, indicate...
1. In this problem, the domain of x is integers. For each of the statements, indicate whether it is TRUE or FALSE then write its negation and simplify it to the point that no ¬ symbol occurs in any of the statements (you may, however, use binary symbols such as ’̸=’ and <). i. ∀x(x+ 2 ≠ x+3) ii. ∃x(2x = 3x) iii. ∃x(x^2 = x) iv. ∀x(x^2 > 0) v. ∃x(x^2 > 0) 2. Let A = {7,11,15}, B...
Indicate whether the following statements are (True) or (False) and correct the False statements: 1. The...
Indicate whether the following statements are (True) or (False) and correct the False statements: 1. The corporate treasurer typically handles both cost accounting and financial accounting. ( ) 2. Marginal analysis states that financial decisions should be made and actions taken only when added benefits are greater than zero. ( ) 3. The conflict between the goal of a firm’s owners and the goal of its non-owner managers is incompatibility. ( ) 4. The sale of either bonds or stocks...
Indicate whether each of the following five statements are True or False. 1) A large p-value...
Indicate whether each of the following five statements are True or False. 1) A large p-value indicates the null hypothesis must be true. 2) Increasing the confidence level decreases the sample size needed to achieve a desired margin of error. 3) Increasing the sample size decreases the power of a hypothesis test. 4) Increasing the significance level increases the power of a hypothesis test. 5) If the interaction term in a two factor experiment is significant (small p-value), the main...
State whether the following statements are True or False. If False, state the correct answer. [4]...
State whether the following statements are True or False. If False, state the correct answer. [4] The frequency of people with diabetes is a more informative statistic than the diabetes prevalence rate. Effective surveillance requires fast action. This is especially true of chronic non-communicable diseases.
indicate whether each of the following statements about allosteric enzymes is true or false: A) they...
indicate whether each of the following statements about allosteric enzymes is true or false: A) they always have quaternary protein structure B) They have two regulatory sites C) regulators can decrease but not increase enzyme activity d) both substrate and regulator often bind at the same site
True or False: Indicate whether each of the following statements is true or false and explain...
True or False: Indicate whether each of the following statements is true or false and explain why. 4. The industry supply curve could be downward sloping in the long run. The market for apartment rentals is in equilibrium when the rent is $1000 per month and the quantity of apartments rented is 2,000. A rent control law is passed that sets the maximum rent at $800. If the elasticity of demand for apartments is 1.2 and the elasticity of supply...
Indicate whether the following statements are true or false and justify the answer. (I) If f...
Indicate whether the following statements are true or false and justify the answer. (I) If f and g are functions defined for all real numbers, and f is an even function, then f o g is also an even function. (II) If a function f, defined for all real numbers, satisfies the the equation f(0) = f(1), then f does not have an inverse function.
Indicate whether the following is true or false. If the answer is false, explain why. 1....
Indicate whether the following is true or false. If the answer is false, explain why. 1. Purchases and sales of securities are never reported as investing activities in a statement of cash flows. TRUE or FALSE 2. Purchases and sales of securities are always reported as financing activiies in a statement of cash flows. TRUE or FALSE
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT