{"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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001493127,0.0001325782,0.0003050244,0.0003749397,0.0003440039,0.0002621114,0.0002543807,0.00003876269,3.353512e-7],"category_scores_gemma":[0.00001618039,0.0000962238,0.00002377661,0.000360265,0.0004779886,0.001371855,0.0001547724,0.0001318508,3.813838e-7],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00005192595,"about_ca_system_score_gemma":0.00005248578,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00001976177,"about_ca_topic_score_gemma":0.00002913853,"domain_scores_codex":[0.9981015,0.0002231429,0.0005130666,0.0003259995,0.0006400605,0.0001962305],"domain_scores_gemma":[0.9985511,0.0003665216,0.0004684699,0.0001166456,0.0002779475,0.0002193187],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.002626213,0.0003235358,0.03992294,0.0006670783,0.0003354429,0.00005638315,0.01119606,0.05369867,0.02571524,0.7577057,0.00105982,0.1066929],"study_design_scores_gemma":[0.001334407,0.001510114,0.2081881,0.0001868557,0.00001622204,0.001575062,0.0002659716,0.780773,0.0001121748,0.005583851,0.0002782602,0.0001759375],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.775033,0.0002512027,0.2231852,0.001222003,0.0001037041,0.0001350697,0.000008294531,0.00001255989,0.00004894823],"genre_scores_gemma":[0.8928648,0.00002618088,0.1069226,0.00009224815,0.00008409028,0.00000105556,0.000001017832,0.000003169961,0.000004821659],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.7521219,"threshold_uncertainty_score":0.3923892,"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."}}