VfyThirdNodeCover$-$to$\_$complete.pyfrom graph import Graphfrom math import floorV$3$NCv $=$ 'VERBOSE: VfyThirdNodeCove$()-$ 'VERBOSE $=$ Truedef printV$($text$)$: if VERBOSE: print$($f$\text{'}\{$V$3$NCv$\}\{$text$\}\text{'})$ returnV$3$NCd $=$ 'DEV: VfyThirdNodeCove$()-$ 'DEV $=$ Falsedef printD$($text$)$: if DEV: print$($f$\text{'}\{$V$3$NCd$\}\{$text$\}\text{'})$ returndef VfyThirdNodeCover$($I$,$S$,$H$)$: if False: # $**$ MIDTERM $2$: Change conditional to something reasonable printV$($f$\text{'}$Invalid solution size: $\{$len$($S$)\}\text{'})$ return 'unsure' if False: printV$($f$\text{'}$Invalid hint size: $\{$len$($H$)\}\text{'})$ return 'unsure' g $=$ Graph$($I$,$ weighted$=$False, directed$=$False$)$ nodes $=$ list$($g$.$nodes.keys$())$ edges $=[$str$($edge$)$ for edge in g$.$edges$()]$ printD$($f$\text{'}$edges: $\{$edges$\}\text{'})$ # H is a white$-$space delimited list of nodes nc $=$ H$.$split$()$ nc$\_$size $=$ len$($nc$)$ # $**$ MIDTERM #$2$: Add other reasons to be unsure. return 'correct'if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$: def test$\_$case$($func$,$I,S$,$H$,$expected,num,comment$=\text{'}\text{'})$: err $=\text{'}**\text{'}$ result $=$ func$($I$,$S$,$H$)$ func$\_$name $=$ str$($func$).$split$()[1]$ func$\_$call $=$ f$\text{'}\text{'}\text{'}\{$func$\_$name$\}("\{$I$\}","\{$S$\}","\{$H$\}")\text{'}\text{'}\text{'}$ if result $==$ expected: err $=\text{'}\text{'}$ e $=$ expected print $($f$\text{'}\{$err$\}$test #$\{$num$\}\{$func$\_$call$\}$: expected $"\{$e$\}",$ received $"\{$result$\}"\text{'})$ print $($f$\text{'}$test #$\{$num$\}$ Explanation: $\{$comment$\}$

$\text{'})$ return num $+1$ F $=$ VfyThirdNodeCover I $=\text{'}$a$,$b a$,$c b$,$c;$2\text{'}$ num $=1$ exp $=$ 'solution too long' num $=$ test$\_$case$($F$,$I,'maybe',$\text{'}$a b$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b a$,$c b$,$c;$1\text{'}$ exp $=\text{'}|\{$a$,$b$\}|=2>$ floor$($len$($nodes$)/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a b$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b a$,$c b$,$c;$2\text{'}$ exp $=$ 'a does not cover b$-$c$\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b a$,$c$\text{'}$ num $=1$ exp $=$ 'a covers all edges, and $|\{$a$\}|=1=$ floor$($len$($nodes$)/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'correct',num,exp$)$ # From PolyReduceThirdNodeCoverToHalfClique I $=\text{'}$a$,$b a$,$c c$,$d$\text{'}$ exp $=\text{'}|\{$a$,$c$\}|>$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a c$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b c$,$d e$,$f$\text{'}$ exp $=\text{'}|\{$a$,$b$,$c$\}|>$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a b c$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b a$,$c a$,$d a$,$e a$,$f f$,$g$\text{'}$ exp $=\text{'}\{$a$\}$ does not cover all the nodes in the graph' num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b a$,$c d$,$e d$,$f d$,$g$\text{'}$ exp $=\text{'}|\{$a$,$c$\}$ does not cover all the nodes in the graph' num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a c$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b a$,$c d$,$e d$,$f d$,$g e$,$h$\text{'}$ exp $=\text{'}|\{$a$,$d$,$e$\}|>$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a d e$\text{'},$'unsure',num,exp$)$ I $=\text{'}$a$,$b b$,$c$\text{'}$ exp $=\text{'}|\{$a$\}|$ does not cover graph' num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'unsure',num,exp$)$ I$=\text{'}$a$,$b a$,$c$\text{'}$ exp $=\text{'}|\{$a$\}|1/3$ nodes in graph' num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'correct',num,exp$)$ I $=\text{'}$a$,$b a$,$c d$,$e d$,$f$\text{'}$ exp $=\text{'}|\{$a$,$d$|=$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a d$\text{'},$'correct',num,exp$)$ I $=\text{'}$a$,$b a$,$c a$,$d a$,$e a$,$f$\text{'}$ exp $=\text{'}|\{$a$\}|$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'correct',num,exp$)$ I $=\text{'}$a$,$b a$,$c d$,$e d$,$f d$,$g$\text{'}$ exp $=\text{'}|\{$a$,$d$\}|$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a d$\text{'},$'correct',num,exp$)$ I $=\text{'}$a$,$b a$,$c a$,$d a$,$e a$,$f a$,$g$\text{'}$ exp $=\text{'}|\{$a$\}|$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'correct',num,exp$)$ I $=\text{'}$a$,$b a$,$c d$,$e d$,$f d$,$g d$,$h$\text{'}$ exp $=\text{'}|\{$a$,$d$\}|$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a d$\text{'},$'correct',num,exp$)$ I $=\text{'}$a$,$b a$,$c a$,$d a$,$e a$,$f a$,$g a$,$h$\text{'}$ exp $=\text{'}|\{$a$\}|$ floor$(|$nodes$|/3)\text{'}$ num $=$ test$\_$case$($F$,$I,'yes',$\text{'}$a$\text{'},$'correct',num,exp$)$

Below is the define thirdnode

expected and actual results in the test cases is a good sign. Bear in mind that stance $I^{\text{'}}$ of Hyon implementation is to map an instance I of ThirdNodeCover onto an stance of Thirdifique, such that $I^{\text{'}}$ is a positive instance of HalfClique iff I is a positive

node cover is a subset of the nodes in an unweighted, undirected graph $($specified as a white ace delimited sequence of edges$),$ such that every edge in the graph has one or both idpoints in a node in the subset.

instance of ThirdNodeCover is an unweighted, undirected graph as defined above. It is a positive tance if the graph contains a node cover subset $S,$ such that $|S|$ floor$($N$/3),$ where $N$ is the mber of nodes in the graph. For example, $\text{'}a,ba,cd,ed,fd,g\text{'}$ is a positive instance of irdNodeCover because it defines a graph with $7$ nodes, $\{a,d\}$ is a node cover subset, and $|\{a,d\}|2=$ floor