csc 520 spring 2024 hw 2 complexity 25 points submit a zip archive con
Search for question
Question
CSC 520 Spring 2024
HW #2

Complexity
25 points
Submit a .zip archive containing 3 files, or each file separately:
• A plain text .txt file that affirms the honor code. For individuals: On my honor as an SFSU
student, I, <name>, have neither given or received inappropriate help with this
homework assignment. For groups: On our honor as SFSU students, we, <names>, have
neither given or received inappropriate help with this homework assignment. All
group members participated in this work, and all concur with the submission.
• A .py Python source code file with your problem 1 solution.
• A .py Python source code file with your problem 2 solution.
1. (12.5 points). An instance of OneColorDup is a whitespace delimited list of edges, separated by a
semicolon (';') from a whitespace delimited list of node colorings. An edge is formatted as two node
names separated by a comma (e.g., "a,b"), and a node coloring as a node name and a color separated by
a colon (e.g., "b:blue"). For example, 'a,b b,c c,d d,a ; a:red b:blue c:yellow d:blue' is an
instance of OneColorDup.
A OneColorDup instance is a positive instance iff it encodes a graph with a directed cycle that goes through
a node of every color in the colorings; no two adjacent nodes in that cycle have the same color; exactly
one color occurs twice; and no color occurs more than two times. For example:
If I 'a,b b,c c, d d,a ;
=
instance of OneColorDup.
a:red b:blue c:yellow d:blue' then 'a,b,c,d' verifies I as a positive
If I = 'a,b b,c c,a d,a ; a:red b:blue c:green d:yellow' then 'a,b,c' cannot verify I as a
positive instance of OneColorDup because none of a, b, or c are yellow nodes.
If I = ''a,b b, c c, d
d,e e,f f,a; a:red b:blue c:red d:blue e:red f:yellow' then
'a,b,c,d,e,f' cannot verify I as a positive instance of OneColorDup because there are 3 red nodes in the
proposed cycle.
Complete VfyOneColorDuptemplate.py, included with the test materials, so that it verifies OneColorDup in
polynomial time. The only required import is graph.py from the WCBC library, also included with the test
materials. An important indication that your changes are successful is that none of the test cases included
with the module are flagged with **, meaning that the actual result differed from the expected one.
The test harness output from VfyOneColorDuptemplate.py. The explanations are hand coded in the test
harness:
** test #1 VfyOneColorDup("a,b b,c c,d d,a; a:red b:blue c:yellow
d:blue","maybe", "a,b,c,d"): expected "unsure", received "correct"
test #1 Explanation: solution too long
** test #32 VfyOneColorDup ("a, b b, c c, d d,a; a:red b:blue c:yellow
d:blue","no","a,b,c,d"): expected "unsure", received "correct"
test #2 Explanation: can't verify negative instance
VERBOSE: VerifyOneColorDup () Cycles must have at least 2 nodes.
test #3 VfyOneColorDup ("a,a; a:red","yes","a"): expected "unsure", received "unsure"
test #3 Explanation: One node does not a cycle make
** test #4 VfyOneColorDup("a,b b,c c,d d,a ; a: red b:blue c:yellow
d:blue","yes","e,a,b,c,d"): expected "unsure", received "correct"
test #4 Explanation: e not in graph
** test #5 VfyOneColorDup ("a, b b, a c, d d,a; a:red b:blue c:yellow
d:blue","yes","a,b,a,d"): expected "unsure", received "correct"
test #5 Explanation: "a" occurs twice
CSC 520 Spring 2024
HW #2 Complexity
1 of 5 ** test #36 VfyOneColorDup("a,b b,d c, d d,a; a:red b:blue c:yellow
d:blue","yes","a,b,c,d"): expected "unsure", received "correct"
test #6 Explanation: No bc edge
** test #37 VfyOneColorDup("a,b b,c c, d
d,a; a red b:blue c:blue
d: yellow", "yes", "a,b,c,d"): expected "unsure", received "correct"
test #7 Explanation: consecutive blues
** test #8 VfyOneColorDup("a,b b,c c, a d,a; a:red b:blue c:green
d:yellow", "yes", "a,b,c"): expected "unsure", received "correct"
test #8 Explanation: no yellow in cycle
** test #9 VfyOneColorDup ("a, b b,c c,d d,e e, f f,a; a:red b:blue c:red d: blue e:red
f:yellow", "yes", "a,b,c,d,e,f"): expected "unsure", received "correct"
test #9 Explanation: 3 reds
** test #10 VfyOneColorDup("a,b b,c c,d d,a; a:red b:blue c:white
d:yellow","yes", "a,b,c,d"): expected "unsure", received "correct"
test #10 Explanation: no color duplicated
test #11 VfyOneColorDup("a,b
b,c c,d d,a; a:red b:blue c: yellow
d:blue","yes","a,b,c,d"): expected "correct", received "correct"
test #11 Explanation: abc traverses every color; no consecutive nodes in cycle same
color; blue occurs twice
In contrast, this is the test harness output from a working version of OneDupNode, which generates
verbose output to explain "unsure" returns.
test #1 VfyOneColorDup("a,b b,c c,d d,a; a:red b:blue c: yellow
d:blue", "maybe", "a,b,c,d"): expected "unsure", received "unsure"
test #1 Explanation: solution too long
VERBOSE: VerifyOneColorDup () solution != "yes"
test #2 VfyOneColorDup("a,b b,c c, d d,a; a:red b:blue c:yellow d:blue",
expected "unsure", received "unsure"
test #2 Explanation: can't verify negative instance
VERBOSE: VerifyOneColorDup ( ) Cycles must have at least 2 nodes.
"no
, "a,b,c,d"):
test #3 VfyOneColorDup("a,a; a:red", "yes","a"): expected "unsure", received "unsure"
test #3 Explanation: One node does not a cycle make
VERBOSE: VerifyOneColorDup() "e" in hint but not graph
DEV: {'a': 'red', 'b': 'blue', 'c': 'yellow', 'd': 'blue'}
test #4 VfyOneColorDup("a,b b,c c,d d,a ; a:red b:blue c:yellow
d:blue","yes","e,a,b,c,d"): expected "unsure", received "unsure"
test #4 Explanation: e not in graph
VERBOSE: VerifyOneColorDup() "a" occurs twice in cycle
test #35 VfyOneColorDup("a,b b,a c, d d,a ; a:red b:blue c: yellow
d:blue", "yes","a,b,a,d"): expected "unsure", received "unsure"
test #5 Explanation: "a" occurs twice
VERBOSE: VerifyOneColorDup () No edge connecting "b" to "c"
DEV: "['c,d', 'a,b', 'b,d', 'd,a']"
test #6 VfyOneColorDup ("a,b b,d c,d d,a; a:red b:blue c: yellow
d:blue","yes","a,b,c,d"): expected "unsure", received "unsure"
test #6 Explanation: No bc edge
CSC 520 Spring 2024
HW #2 Complexity
2 of 5 VERBOSE: VerifyOneColorDup() Adjacent nodes with color "blue"
test #7 VfyOneColorDup("a,b b,c c,d d,a; a:red b:blue c:blue
d: yellow", "yes", "a,b,c,d"): expected "unsure", received "unsure"
test #7 Explanation: consecutive blues
VERBOSE: VerifyOneColorDup() No "yellow" colored nodes in cycle.
test #8 VfyOneColorDup("a,b b,c c, a d,a; a:red b:blue c:green d:yellow","yes","a,b,c"):
expected "unsure", received "unsure"
test #8 Explanation: no yellow in cycle
VERBOSE: VerifyOneColorDup() "red" occurs 3 times in cycle
test #9 VfyOneColorDup("a,b b,c c,d d,e e,f f,a; a:red b:blue c:red d:blue e:red
f:yellow","yes","a,b,c,d,e,f"): expected "unsure", received "unsure"
test #9 Explanation: 3 reds
VERBOSE: VerifyOneColorDup () No color duplicated
test #10 VfyOneColorDup ("a,b b,c c,d d,a; a:red b:blue c: white
d: yellow", "yes", "a,b,c,d"): expected "unsure", received "unsure"
test #10 Explanation: no color duplicated
test #11 VfyOneColorDup ("a,b b,c
c, d
d,a; a:red b:blue c: yellow
d:blue","yes","a,b,c,d"): expected "correct", received "correct"
test #11 Explanation: abc traverses every color; no consecutive nodes in cycle same
color; blue occurs twice
2. (12.5 points) A node cover is a subset of the nodes in an unweighted, undirected graph, specified as a
white space delimited sequence of edges, such that every node in the encoded graph has at least one
end point in the node cover subset. For example, the graph 'a,b a,c b,c' has a node cover of size 2:
{a,b}.
An instance of HasNodeCover is a graph encoding as specified above, separated by a ";" from the
maximum acceptable node cover size. For example, 'a,b a,c b, c; 2' is an instance of HasNodeCover.
An instance of HasNodeCover is a positive instance iff it encodes a graph with a node cover no larger than
the specified maximum. For example, 'a,b a,c b,c; 2' is a positive instance of HasNodeCover, but 'a, b
a,c b,c; 1' is a negative instance since there is no single node that covers the graph.
An independent set is a subset of the nodes in an unweighted, undirected graph, specified as a white
space delimited sequence of edges, such that there are no edges between any two nodes in the
independent set. For example, the graph "a,a a,c a,d a,e b,c b,d b,e c, d c,e d,e" has an
independent set of size 2, {a,b} since there is no link connecting nodes a and b. Note that loop back nodes
are not considered when specifying independent sets.
An instance of HalfIndependentSet is also an unweighted, undirected graph specified as a series of edges.
For example, "a,d a,e a,f b,d b,e b,f c,c c,f e,f".
A HalfIndependentSet instance is a positive instance iff at least half the nodes in the graph form an
independent set. For example, "a,d a,e a,f b,d b,e b,f c,c c,f e, f" is a positive instance because
{a, b, c} forms an independent set of size 3, out of a total of 6 graph nodes. But "a,a a,c a,d a,e b,b
b,c b,d b,e c, d c,e d,e" is a negative instance, because it has no independent set larger than 2, which
is one less than half the number of the nodes in the graph.
Complete the template file ConvertNodeCoverToHalfIndependentSettemplate.py to prove
HalfIndependentSet is NPhard by polyreduction from HasNodeCover. Add a comment at the end
arguing that your code is a valid proof; you may wish to consider Karp's 1972 paper, in which he showed
that solving NodeCover was as hard as solving SAT (see below for copies of presentation slides on the
Node Cover, Clique, and Independent Set problems). You are welcome to call
ConvertCliqueToHalfIndependentSet (in test materials), and ncToClique (defined in template), but are not
required to do so. It is possible to make the needed code changes in a handful of lines. The test harness
works in the usual way.
CSC 520 Spring 2024
HW #2 Complexity
3 of 5 Output from ConvertNodeCoverToHalfIndependentSettemplate.py before any changes, with unexpected
results flagged by **. Note the verbose output from VfyHalfIndependentSet.py, included with the test
materials. If you do not want to see verbose output from any module, just set verbose to false at the top
of the file.
VERBOSE: vfyNCViaVfyHalfIndependentSet(): "z" is not a valid int encoding
test #1 vfyNCViaVfyHalfIndependentSet("a,b a,c a,d a,e b, f;z", "yes", "a f"): expected
"unsure", received "unsure"
test #1 Explanation: "z" is not an encoding of a decimal integer
VERBOSE: ConvertNodeCoverToHalf IndependentSet() node covering size "0" < 1
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "b ecd"
VERBOSE: VfyHalfIndependentSet() ""becd " not independent set, edge "e,c" exists"
test #2 vfyNCViaVfyHalfIndependentSet("a,b a,c a,da, e b, f;0", "yes", "a f"): expected
"unsure", received "unsure"
test #2 Explanation: node cover subset must be greater than 0
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "becd "
test #3 vfyNCViaVfyHalfIndependentSet("a,b a,c a,d a,e b,f;2", "yes", "a f"): expected
"correct", received "correct"
test #3 Explanation: {a f} is node cover
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "e b c d g
"
** test #4 vfyNCViaVfyHalfIndependentSet("a,b a,c a,d a, e b,f b,g;2", "yes", "a f"):
expected "unsure", received "correct"
test #4 Explanation: {a f} is not a node cover
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "e f "
VERBOSE: VfyHalfIndependentSet() 2 nodes in hint, 3 needed
** test #5 vfyNCViaVfyHalfIndependentSet("a,b b,c c,d d,e d,f;4", "yes", "a b c d"):
expected "correct", received "unsure"
test #5 Explanation: {a b c d} is node cover
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "e f g
VERBOSE: VfyHalfIndependentSet() 3 nodes in hint, 4 needed
"
test #6 vfyNCViaVfyHalfIndependentSet("a,b a,c a,d a,e b,f b,g; 4", "yes", "a b c d"):
expected "unsure", received "unsure"
test #6 Explanation: {a b c d } is not a node cover
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "e f "
VERBOSE: VfyHalfIndependentSet() 2 nodes in hint, 3 needed
test #7 vfyNCViaVfyHalfIndependentSet("a,b b,c c,d d,e d,f;3", "yes", "a b c d"): expected
"unsure", received "unsure"
test #7 Explanation: {a b c d} > 3
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "b c "
test #8 vfyNCViaVfyHalfIndependentSet("a,b a,c;1", "yes", "a"): expected "correct",
received "correct"
test #8 Explanation: {a} is a node cover
DEV: vfyNCViaVfyHalfIndependentSet(): hint for VfyHalfIndependentSet: "a c
"
** test #9 vfyNCViaVfyHalfIndependentSet("a,b a,c;1", "yes", "b"): expected "unsure",
received "correct"
test #9 Explanation: {b} is not a node cover
CSC 520 Spring 2024
HW #2 Complexity
4 of 5 CLIQUE
Input: graph G, positive integer k
Karp's definition of Clique
Each node in a clique is connected to all the other
Property: G has a set of k mutually adjacent nodes. nodes in the clique.
NODE COVER
Input: graph G', positive integer
Property: There is a set RC N' such that R <l and every
arc is incident with some node in R. [N' is the set of nodes in
the graph G'.]
Karp's reduction
from Clique to
Node Cover
CLIQUE OC NODE COVER
Karp's definition of Node Cover
In other words, the node
cover of a graph is a set of
vertices that includes at
least one endpoint of every
edge of the graph.
G' is a complement of G
if G' has an edge
everywhere
G' is the complement of G. G doesn't, and vice
1 = N − k

versa.
R, the number of nodes to cover G' = the number of nodes  the size of the clique.
Example of Clique ≤p Node Cover
P
Exercise: prove this maps
positive to positive and
negative to negative
lique a set of nodes
Ich that every node in
e set is connected to
I the others. (Black
odes in G.)
Node cover a set of
nodes including at least
one end point of every
edge in the graph.
(White nodes in G'.)
Clique instance G with k = 4
Node Cover instance G' with 1 =64=2
Node Cover Sp Independent Set
CSC 520 Spring 2024
IndependentSetD(g,n) = 3s( (S is a subset of the nodes in
graph g) and (S ≥n) and (no node in S is adjacent to
any other node in S) ). In other words, there are no edges
connecting any two nodes in S.
For example, if g₁ = 'a, e a,b c, e d, e', then 'g,; '3' is a
positive instance of IndependentSet because there are no
edges connecting nodes b, c, and d. But g,, '4' is a
negative instance. And if g₂ = 'a, e a,b c,d c,e d,e',
then g₁, '3' is also a negative instance of IndependentSet,
since the addition of the edge c,d means that b, c, and d
are not completely disconnected from each other.
The diagram, taken from the previous slide, shows a node cover subset (white disks). Every
edge in the diagram must have a white disk as one or both end points, so there can be no
edge connecting two blacks disks.
.. the black disks form an independent set.
HW #2 Complexity
5 of 5