{"id":"W2028556486","doi":"10.1007/s00224-011-9333-8","title":"The Complexity of the List Homomorphism Problem for Graphs","year":2011,"lang":"en","type":"article","venue":"Theory of Computing Systems","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":25,"is_retracted":false,"has_abstract":false,"ca_institutions":"Université Laval; Concordia University; McGill University","funders":"Engineering and Physical Sciences Research Council","keywords":"Constraint satisfaction problem; Homomorphism; Combinatorics; Mathematics; Algebraic number; Discrete mathematics; Computational complexity theory; Graph; Computer science; Algorithm","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.003277341,0.001174372,0.002782082,0.001982537,0.003345001,0.01116969,0.005640374,0.00473228,0.02155034],"category_scores_gemma":[0.03572892,0.001421949,0.00209412,0.004488461,0.004646433,0.03287236,0.004825827,0.007651328,0.002158305],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.005304914,"about_ca_system_score_gemma":0.004026383,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.005426764,"about_ca_topic_score_gemma":0.004683965,"domain_scores_codex":[0.9943113,0.001967827,0.0002625806,0.001099062,0.001311222,0.001048093],"domain_scores_gemma":[0.9401779,0.05118098,0.002067924,0.003156691,0.001531927,0.00188467],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.001831694,0.0007348203,0.005048492,0.001256622,0.0002192459,0.0004312247,0.001682693,0.09243888,0.002989737,0.780683,0.05098648,0.06169703],"study_design_scores_gemma":[0.0001279274,0.00003601535,0.0005771401,0.00003483265,0.00005519955,0.0001468481,0.0002545954,0.08144329,0.0007004593,0.9145451,0.002039259,0.00003934087],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.5650511,0.005297372,0.2872186,0.04927946,0.0008511633,0.0003500008,0.006727438,0.002032561,0.08319226],"genre_scores_gemma":[0.9281599,0.002470081,0.04367787,0.001595624,0.00157005,0.0003233699,0.004295817,0.0007125908,0.01719475],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.02155034,"threshold_uncertainty_score":0.07209301,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.09207204870786918,"score_gpt":0.2876164445971816,"score_spread":0.1955443958893124,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}