COMPUTER VISION SYSTEMS
COMPUTER VISION SYSTEMS CAP 6411
University of Central Florida
Popular in Course
Popular in System Engineering
This 3 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 6411 at University of Central Florida taught by Staff in Fall. Since its upload, it has received 14 views. For similar materials see /class/227217/cap-6411-university-of-central-florida in System Engineering at University of Central Florida.
Reviews for COMPUTER VISION SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
PARTITION INTO GLOBAL DEFENSIVE ALLIANCESPGDA is NPComplete NOT ALL EQUAL 3SAT NAE3SAT Input A set U u1u2un of variables and a collection C C C Cm of clauses 1 2 over U where each clause contains exactly three literals variables or their complements with no literal appearing more than once in any given clause Question Is there a truth assignment that makes one or two but not all three literals true in each clause We may assume that each literal appears in at least one of the clauses otherwise for each literal u j that does not appear in any of the clauses we can add another variable y and two clauses C u jy and C u j7 These two clauses are satis ed by any truth assignment and do not affect the truth assignment of the original problem Theorem Given a graph G the problem of deciding whether the graph G has a partition into global defensive alliances is NP Complete Proof Given an instance of NAE3SAT with n variables and m clauses we transform it into an instance of PGDA by constructing a graph G VE as follows For a literal u e U U U let Cu be the set of clauses that contains u Let V QUXURUT where Qquue ULJU X xllSi S n R U atU5 Ru and T U ISjSmTJ For all u e U Ru r ul Si S 2 and for all e U Ru i3 ul Si S Also for all C e C T If atj btj 0M C 61 bc For each literal u e U UU we create a star Su where VSu qu URu and the vertex qu forms the center of the star For each x e X we add edges xlqu1 and xlqt71 in graph G For each clause C e C we setup atriangle T in V and for each vertex t ue T add an edge qu tj in graph G The order of the constructed graph V 5n 6m and the size ofthe graph E 4n 9m which is polynomially related to the size of NAE3SAT problem We now claim that the constructed graph G has a partition into global defensive alliances if and only if the given instance of NAE3SAT has a satisfying truth assignment The proof of the claim is as follows 3 Suppose that the given instance of NAE3SAT has a satisfying truth assignment f U gt 01 We define a partition ofthe vertex set V A1 UA2 as follows A UEMAfutlqu U x l u e U U R07 N US it u o T l and A2 V A We now show that bothA1 and A2 are global defensive alliances in graph G Consider any ve Ar 6 12 and consider five cases Case 1 v qu for some u e U From the partitioning scheme Nv m A x U LJISJSM t u m T ie Nv WA 1Cu X Similarly Nvn V A Ru ie Nvn V A 2 Cu NvmA 2 NvmV A 1 Case 2 v qu for some u e U Again from the partitioning scheme Nv m A U15 t u m T ie Nv WA C14 Nv V ARu ie Nv V A C14 NvmA 2 NvnV A 1 Case 3 ve Ru for some u e U U U Then by construction and partitioning scheme Nv NA Q and Nv m V A qu Hence NvmA 2 NvmV A 1 Case 4 v x Then Nv NA qu and Nv V A qt7 Hence NvmA 2 NvnV A 1 Case 5 v t u for some u e U U U By construction and partitioning scheme N v WA 2 qu and by the property of satisfying truth assignment of NAE3SAT Nvm V Ag T t u Hence Nv A 2 Nv V A 1 Hence Similarly Hence Since for all v e A where r 6 12 Nv WA 2 Nv V A X 1 A is a defensive alliance It is also easy to see that NA V Hence both A1 and A2 are global defensive alliances and they partition the vertex set of graph G lt Suppose now that the constructed graph G has a vertex partition A1A2 such that both A1 and A2 are global defensive alliances Since each vertex x e X is adjacent to only two vertices qu and q exactly one of these vertices must be in the same set A r 6 01 otherwise NV A g V x which is contrary to V A being a global defensive alliance Suppose that qu e A for some u e U UU and r 6 01 It is easy to see that Ru 0 A Q Suppose to the contrary and let w e Ru A Since Nw qu wg A NV A g V w which is contrary to V A being a global defensive alliance This also implies that for all qu e A Nqu V A Q Ru Consider two cases Rm 2 Since Nqu 2 Cu Case 1 u e U then by construction Cu X 2 Thus by above implication we NQWDoW A dm have 4 and since A is a defensive alliance we must have N W lo A N W 1 Ru qu x U Us in u o T 1 Ru1 Cu11 Also by Case 1 x e Nqu1 V Ar Thus Nqu1 V Ar 2 C11 Nqul 2 Cul 2 and since A is a defensive alliance we must have N W lo A N W lRu x qu U Us in u o T 1 Case 2 u e 17 then by construction 1 Since The above arguments show the following lemma Lemma 1 For all u e U U17 ifqu1e A for re 01 then for all tju1e T 13 Smtju1eAr We now define a truth assignment f U gt 01 such that ful 1 if and only if qul 6 A1 We claim that f is a truth assignment that makes one or two but not all three literals true in each clause Suppose to the contrary and let C j 61 b c be a clause such that fa fb From the definition off qa qb qcg A r 6 01 and from Lemma 1 T If a t b tj 0g A By construction of graph G NlTj J Nltj aJU Nltj bJU Nltj T U qa qb qc which is contrary to V A being a global defensive alliance