{"id":"W3000817392","doi":"10.1007/978-3-030-39219-2_5","title":"Approximating Modular Decomposition Is Hard","year":2020,"lang":"en","type":"book-chapter","venue":"Lecture notes in computer science","topic":"Advanced Graph Theory Research","field":"Computer Science","cited_by":4,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Toronto","funders":"Agence Nationale de la Recherche","keywords":"Modular design; Computer science; Modular decomposition; Decomposition; Algebraic number; Graph; Time complexity; Data structure; Neighbourhood (mathematics); Discrete mathematics; Theoretical computer science; Algorithm; Mathematics; Line graph; Pathwidth","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.0009352936,0.002002113,0.002152234,0.001338726,0.00167115,0.004802217,0.002059093,0.001737992,0.02409184],"category_scores_gemma":[0.006952662,0.001147493,0.001462502,0.002903688,0.00219186,0.008430207,0.004697369,0.007668088,0.006114561],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.001785375,"about_ca_system_score_gemma":0.0007302723,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0006764241,"about_ca_topic_score_gemma":0.001112063,"domain_scores_codex":[0.9986975,0.0002371615,0.00005560995,0.0003324964,0.000434239,0.0002429601],"domain_scores_gemma":[0.995962,0.002207794,0.0002494005,0.0008956598,0.0003453036,0.0003398523],"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.0006592943,0.0002448283,0.001352596,0.000752162,0.0001134525,0.0002591055,0.0004781331,0.01495665,0.006060093,0.7502289,0.08981717,0.1350776],"study_design_scores_gemma":[0.00003891942,0.00003375469,0.0003441004,0.00003658478,0.00003463685,0.0001831975,0.0001030916,0.01900705,0.001153044,0.9678971,0.01115554,0.0000128566],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"other","genre_gemma":"empirical","genre_scores_codex":[0.2531123,0.003782341,0.3336505,0.01527351,0.002030067,0.0002494387,0.002663248,0.002561656,0.3866769],"genre_scores_gemma":[0.7407411,0.003610296,0.08546185,0.003146621,0.001897182,0.0004012324,0.004375364,0.001721768,0.1586446],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.02409184,"threshold_uncertainty_score":0.08059525,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.02567637745108079,"score_gpt":0.2885644326627407,"score_spread":0.2628880552116599,"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."}}