core (907B)
1 # Core 2 3 The [core] of an [instance] A is a [subinstance] B of A such that there is no [homomorphism] from B to a strict [subinstance] B' of B 4 - this is unique up to [isomorphism] 5 - it is equal to A if there is no [endomorphism] from A to a strict [subinstance] of A 6 7 [computational_problem] of computing the core: 8 - checking if a [graph] is its own core 9 - clearly in [coNP] (guess the [homomorphism]) 10 - [conp_complete] 11 - https://cstheory.stackexchange.com/questions/2733/what-is-the-best-exact-algorithm-to-compute-the-core-of-a-graph 12 - checking if input [graph] G is core of input [graph] H 13 - is in [dp]: 14 - guess existence of [homomorphism] 15 - guess inexistence of other [homomorphism] 16 - is [dp_complete] by [fagin2005data2] 17 - https://cstheory.stackexchange.com/questions/2733/what-is-the-best-exact-algorithm-to-compute-the-core-of-a-graph 18 19 Up: [homomorphism] 20 21 See also: [chase_core]