{"id":"W256842657","doi":"10.1613/jair.4030","title":"Inapproximability of Treewidth and Related Problems","year":2014,"lang":"en","type":"article","venue":"Journal of Artificial Intelligence Research","topic":"Bayesian Modeling and Causal Inference","field":"Computer Science","cited_by":64,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Toronto","funders":"Natural Sciences and Engineering Research Council of Canada","keywords":"Treewidth; Partial k-tree; Pathwidth; Combinatorics; Tree-depth; Graphical model; Tree decomposition; Mathematics; Chordal graph; Discrete mathematics; Computer science; Graph; 1-planar graph; Line graph; Artificial intelligence","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.008166771,0.00009223441,0.0002703027,0.0003428858,0.0001145509,0.0001313803,0.0008682967,0.00009461852,0.00001804787],"category_scores_gemma":[0.001196999,0.00007240948,0.0000749504,0.0007994699,0.0003929489,0.0004071852,0.0002102956,0.0006711581,0.00001238669],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00003819533,"about_ca_system_score_gemma":0.0001956339,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00004391098,"about_ca_topic_score_gemma":0.000008779103,"domain_scores_codex":[0.9973124,0.0005187082,0.0008452017,0.0002288936,0.0007734891,0.0003213672],"domain_scores_gemma":[0.9974067,0.0005864053,0.0002615641,0.0003571211,0.001208471,0.0001796922],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.00002879851,0.0002162956,0.0003352184,0.0000594655,0.00001867627,0.000005005416,0.001728153,0.0008782649,0.01107477,0.2780133,0.00004459376,0.7075974],"study_design_scores_gemma":[0.0000374988,0.0009944633,0.0003288011,0.0001257961,0.000003980523,0.00005959644,0.0001978099,0.292876,0.03152817,0.6736307,0.0001238805,0.00009335026],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1798343,0.0002368212,0.8172351,0.001319307,0.0001487264,0.0001018744,3.705655e-7,0.00001255715,0.001111044],"genre_scores_gemma":[0.984411,0.0001114738,0.01537368,0.000009208809,0.00005332656,0.000001599374,9.01411e-8,0.000005199523,0.00003439263],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.8045768,"threshold_uncertainty_score":0.2952773,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.142345972613428,"score_gpt":0.382805798384195,"score_spread":0.240459825770767,"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."}}