{"id":"W2051028069","doi":"10.1016/j.jcss.2004.07.003","title":"A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results","year":2005,"lang":"en","type":"article","venue":"Journal of Computer and System Sciences","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":30,"is_retracted":false,"has_abstract":false,"ca_institutions":"Simon Fraser University","funders":"","keywords":"Computational complexity theory; Bipartite graph; Compaction; Mathematics; Equivalence (formal languages); Combinatorics; Computational problem; Constraint satisfaction problem; Computer science; Chordal graph; Time complexity; Discrete mathematics; Theoretical computer science; Graph; Algorithm; Artificial intelligence","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[{"model":"gemma","categories":[],"domain":null,"study_design":"theoretical_or_conceptual","genre":"empirical","about_ca_system":false,"about_ca_topic":false,"confidence":"high","status":"direct model label, unvalidated"},{"model":"gpt","categories":[],"domain":null,"study_design":"theoretical_or_conceptual","genre":"other","about_ca_system":false,"about_ca_topic":false,"confidence":"high","status":"direct model label, unvalidated"}],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.004157807,0.004156761,0.006141479,0.004064625,0.003259698,0.00930065,0.00871875,0.006228596,0.01937025],"category_scores_gemma":[0.035438,0.001879726,0.007871991,0.007280801,0.004935041,0.02678662,0.006804666,0.01116559,0.003256361],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.003927215,"about_ca_system_score_gemma":0.004283153,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002505323,"about_ca_topic_score_gemma":0.002567989,"domain_scores_codex":[0.9922769,0.001525708,0.0005384776,0.002135896,0.001837747,0.001685324],"domain_scores_gemma":[0.9446276,0.03820443,0.003004768,0.009690098,0.002569543,0.001903594],"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.002541812,0.001337966,0.006144744,0.002570001,0.0004145612,0.0004446494,0.001233979,0.1157208,0.01111751,0.5184485,0.09558494,0.2444405],"study_design_scores_gemma":[0.0002277699,0.0002696228,0.00242302,0.0001219576,0.0002506103,0.0006149181,0.0003087464,0.1723507,0.004117335,0.8110554,0.00812298,0.0001369731],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2139962,0.00822619,0.6965058,0.01395071,0.001029609,0.0009787044,0.006574346,0.004338326,0.05440011],"genre_scores_gemma":[0.6303601,0.00780705,0.2880017,0.005126409,0.005697992,0.001777112,0.01846251,0.003138605,0.03962855],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01937025,"threshold_uncertainty_score":0.06479996,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.1057088892842839,"score_gpt":0.3314450610096022,"score_spread":0.2257361717253184,"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."}}