The Max Cut problem is given a undirected graph G(V, E), finding a set S so...
The Max Cut problem is given a undirected graph G(V, E), finding a set S so that the number of edges that go between S and V − S is maximum. This is an NPC problem.
a) Show that there is always a max cut of size at least |E|/2. Hint: Decide where to put vertices according to if they have more neighbors in S or V − S.
Homework Answers
We will split the vertices into sets S1 and S2. Start with all vertices on one side of the cut. Now, if you can switch a vertex to a different side so that it increases the number of edges across the cut, do so. Repeat this action until the cut can no longer be improved by this simple switch. We switch vertices at most |E| times (since each time, the number of edges across the cut increases).
Add Answer to:
The Max Cut problem is given a undirected graph
G(V, E), finding a set S so...
1. Here is a randomized algorithm for MAX-CUT on an undirected graph G = (V,E): 1....
1. Here is a randomized algorithm for MAX-CUT on an undirected graph G = (V,E): 1. Initialize S to be the empty set 2. For every vertex v in V: 3. Put v into S with probability 1/2 4. Let T = V\S be the complement of S 5. Output (S,T) Recall that E(S, T) CE is the set of edges that have one endpoint in S and the other endpoint in T, ie., E(S, T) = {(u, u) :...
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph...
Let G = (V;E) be an undirected and unweighted graph. Let S be a subset of the vertices. The graph induced on S, denoted G[S] is a graph that has vertex set S and an edge between two vertices u, v that is an element of S provided that {u,v} is an edge of G. A subset K of V is called a killer set of G if the deletion of K kills all the edges of G, that is...
Question 1: Given an undirected connected graph so that every edge belongs to at least one...
Question 1: Given an undirected connected graph so that every edge belongs to at least one simple cycle (a cycle is simple if be vertex appears more than once). Show that we can give a direction to every edge so that the graph will be strongly connected. Question 2: Given a graph G(V, E) a set I is an independent set if for every uv el, u #v, uv & E. A Matching is a collection of edges {ei} so...
2. Let G = (V, E) be an undirected connected graph with n vertices and with...
2. Let G = (V, E) be an undirected connected graph with n vertices and with an edge-weight function w : E → Z. An edge (u, v) ∈ E is sparkling if it is contained in some minimum spanning tree (MST) of G. The computational problem is to return the set of all sparkling edges in E. Describe an efficient algorithm for this computational problem. You do not need to use pseudocode. What is the asymptotic time complexity of...
Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and...
Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and an integer k, return a clique of size k as well as an independent set of size k, provided both exist.
2) Let G ME) be an undirected Graph. A node cover of G is a subset...
2) Let G ME) be an undirected Graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover MNC) is one with the lowest number of vertices. For example {1,3,5,6is a node cover for the following graph, but 2,3,5} is a min node cover Consider the following Greedy algorithm for this problem: Algorithm NodeCover (V,E) Uempty While...
7. Graphs u, u2, u3, u4, u5, u6} and the (a) Consider the undirected graph G...
7. Graphs u, u2, u3, u4, u5, u6} and the (a) Consider the undirected graph G (V, E), with vertex set V set of edges E ((ul,u2), (u2,u3), (u3, u4), (u4, u5), (u5, u6). (u6, ul)} i. Draw a graphical representation of G. ii. Write the adjacency matrix of the graph G ii. Is the graph G isomorphic to any member of K, C, Wn or Q? Justify your answer. a. (1 Mark) (2 Marks) (2 Marks) b. Consider an...
Problem 5. (15 marks) Given a connected, undirected, weighted graph G- (V, E), define the cost...
Problem 5. (15 marks) Given a connected, undirected, weighted graph G- (V, E), define the cost of a spanning tree to be the maximum weight among the weights associated with the edges of the spanning tree. Design an efficient algorithm to find the spanning tree of G which maximize above defined cost What is the complexity of your algorithm.
Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V},...
Definition: Given a Graph \(\mathrm{G}=(\mathrm{V}, \mathrm{E})\), define the complement graph of \(\mathrm{G}, \overline{\boldsymbol{G}}\), to be \(\bar{G}=(\mathrm{V}, E)\) where \(E\) is the complement set of edges. That is \((\mathrm{v}, \mathrm{w})\) is in \(E\) if and only if \((\mathrm{v}, \mathrm{w}) \notin \mathrm{E}\) Theorem: Given \(\mathrm{G}\), the complement graph of \(\mathrm{G}, \bar{G}\) can be constructed in polynomial time. Proof: To construct \(G\), construct a copy of \(\mathrm{V}\) (linear time) and then construct \(E\) by a) constructing all possible edges of between vertices in...
4. The NOT-ALL-EQUAL 3SAT problem is defined as follows: Given a 3-CNF formula F, is there...
4. The NOT-ALL-EQUAL 3SAT problem is defined as follows: Given a 3-CNF formula F, is there a truth assignment for the variables such that each clause has at least one true literal and at least one false literal? The NOT-ALL-EQUAL 3SAT problem is NP-complete. This question is about trying to reduce the NOT-ALL-EQUAL 3SAT problem to the MAX-CUT problem defined below to show the latter to be NP-complete. A cut in an undirected graph G=(V.E) is a partitioning of the...
1. Here is a randomized algorithm for MAX-CUT on an undirected graph G = (V,E): 1. Initialize S to be the empty set 2. For every vertex v in V: 3. Put v into S with probability 1/2 4. Let T = V\S be the complement of S 5. Output (S,T) Recall that E(S, T) CE is the set of edges that have one endpoint in S and the other endpoint in T, ie., E(S, T) = {(u, u) :...
2) Let G ME) be an undirected Graph. A node cover of G is a subset U of the vertex set V such that every edge in E is incident to at least one vertex in U. A minimum node cover MNC) is one with the lowest number of vertices. For example {1,3,5,6is a node cover for the following graph, but 2,3,5} is a min node cover Consider the following Greedy algorithm for this problem: Algorithm NodeCover (V,E) Uempty While...
7. Graphs u, u2, u3, u4, u5, u6} and the (a) Consider the undirected graph G (V, E), with vertex set V set of edges E ((ul,u2), (u2,u3), (u3, u4), (u4, u5), (u5, u6). (u6, ul)} i. Draw a graphical representation of G. ii. Write the adjacency matrix of the graph G ii. Is the graph G isomorphic to any member of K, C, Wn or Q? Justify your answer. a. (1 Mark) (2 Marks) (2 Marks) b. Consider an...
Problem 5. (15 marks) Given a connected, undirected, weighted graph G- (V, E), define the cost of a spanning tree to be the maximum weight among the weights associated with the edges of the spanning tree. Design an efficient algorithm to find the spanning tree of G which maximize above defined cost What is the complexity of your algorithm.
4. The NOT-ALL-EQUAL 3SAT problem is defined as follows: Given a 3-CNF formula F, is there a truth assignment for the variables such that each clause has at least one true literal and at least one false literal? The NOT-ALL-EQUAL 3SAT problem is NP-complete. This question is about trying to reduce the NOT-ALL-EQUAL 3SAT problem to the MAX-CUT problem defined below to show the latter to be NP-complete. A cut in an undirected graph G=(V.E) is a partitioning of the...
Most questions answered within 3 hours.
-
New Air Heating and Cooling, manufactures furnaces and central
air units. The company pride itself on...
asked 2 minutes from now -
A coach uses a new technique to train gymnasts. Seven
gymnasts were randomly selected and their...
asked 1 hour ago -
While rotating the tires on your car you notice a rock [mass =
0.1 Kg] stuck...
asked 3 hours ago -
Using MARS simulator, write MIPS programs according to
the following scenarios: Receive a positive integer number...
asked 5 hours ago -
An object in front of a concave mirror has a real image that is
11.5 cm...
asked 5 hours ago -
Consider the reaction, C3 H8 + O2 --> CO2 + H2O. How many
moles of O2...
asked 7 hours ago -
You and your opponent both roll a fair die. If you both roll the
same number,...
asked 8 hours ago -
In a study of the accuracy of fast food drive-through orders,
Restaurant A had 257 accurate...
asked 8 hours ago -
Identify and describe in detail the four categories of
institutions that could be included in a...
asked 8 hours ago -
In python
class Customer:
def __init__(self, customer_id, last_name, first_name, phone_number, address):
self._customer_id = int(customer_id)
self._last_name =...
asked 8 hours ago -
What is an example of a limitation in implementing a new
ERP system and how it...
asked 8 hours ago -
In a section of 9.7cm of an artery with a radius of 2.6mm there
is a...
asked 8 hours ago