{"id":"W7118052205","doi":"","title":"Thin Tree Verification is coNP-Complete","year":2025,"lang":"","type":"article","venue":"ArXiv.org","topic":"Complexity and Algorithms in Graphs","field":"Computer Science","cited_by":0,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"","keywords":"K-ary tree; Interval tree; Tree (set theory); Graph; Segment tree; Gomory–Hu tree; Kruskal's algorithm; Spanning tree","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.003007108,0.001317157,0.001998544,0.0007816916,0.00315571,0.004417525,0.003320511,0.002419155,0.01405156],"category_scores_gemma":[0.02614493,0.00173754,0.002911785,0.002064127,0.002379393,0.01148121,0.004972908,0.005098236,0.003918455],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002111976,"about_ca_system_score_gemma":0.005487541,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.003835244,"about_ca_topic_score_gemma":0.005944712,"domain_scores_codex":[0.9946445,0.0008634078,0.0003759703,0.001561972,0.001629219,0.0009250126],"domain_scores_gemma":[0.9605026,0.02578367,0.002111403,0.007212577,0.003380135,0.001009598],"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.003493461,0.001295462,0.01600922,0.004667715,0.0006761979,0.002884201,0.001772909,0.2224253,0.04424951,0.2973031,0.1452184,0.2600045],"study_design_scores_gemma":[0.0002524386,0.00014329,0.001529226,0.0001473239,0.0001477303,0.001086861,0.000717645,0.3328184,0.01365066,0.6322852,0.01715931,0.0000618382],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2613687,0.001447006,0.6406479,0.01890643,0.0007997974,0.001240824,0.01485151,0.01260454,0.04813318],"genre_scores_gemma":[0.7032663,0.0009008136,0.2635875,0.002861216,0.0003243655,0.0007627903,0.01401599,0.001706955,0.0125741],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01405156,"threshold_uncertainty_score":0.04700714,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.0661122184933786,"score_gpt":0.2855311649564319,"score_spread":0.2194189464630533,"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."}}