 # 算法代写 | Introduction to Algorithms Homework 10

Ground Rules

• The homework is worth 5 points (out of a total of 100 points you can accumulate in this course).

• The homework is to be done and submitted individually. You may discuss homework problems with at most one other person from either section (and mention this person’s name on your submission), but you must write up solutions on your own.

• You are not allowed to consult any material outside of assigned textbooks and material the instructors post on the course websites. In particular, consulting the internet will be considered plagiarism and penalized appropriately.

• The homework is due at 11:59 PM on the due date. No extensions to the due date will be given under any circumstances.

• Homework must be submitted electronically on canvas. We will not accept paper submissions. Canvas accepts ﬁles in pdf/doc/jpeg formats.

Problem 1 (Worth: 5 points. Page limit: 1 sheet; 2 sides)

A subset S of vertices in an undirected graph G is called triangle-free if, for every triple of vertices u, v, w ∈ S, at least one of the three edges (u, v), (u, w), (v, w) is absent from G.

The problem Large Triangle-Free Subset (LTFS) takes as input a graph G and a number k, and outputs whether G has a triangle free subset of size ≥ k. Prove that LTFS is NP-Complete. E-mail: [email protected]  微信:itcsdx 