{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,22]],"date-time":"2025-11-22T11:17:39Z","timestamp":1763810259123,"version":"3.37.3"},"reference-count":37,"publisher":"World Scientific Pub Co Pte Ltd","issue":"02","funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["26240034"],"award-info":[{"award-number":["26240034"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["26540125"],"award-info":[{"award-number":["26540125"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25730005"],"award-info":[{"award-number":["25730005"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["25250028"],"award-info":[{"award-number":["25250028"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,2]]},"abstract":"<jats:p> We consider the maximum common connected edge subgraph problem and the maximum common connected induced subgraph problem for simple graphs with labeled vertices (or labeled edges). The former is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs. The latter is to find a common connected induced subgraph with the maximum number of vertices. We prove that both problems are NP-hard for 3-outerplanar labeled graphs even if the maximum vertex degree is bounded by 4. Since the reductions used in the proofs construct graphs with treewidth at most 4, both problems are NP-hard also for such graphs, which significantly improves the previous hardness results for graphs with treewidth 11. We also present improved exponential-time algorithms for both problems on labeled graphs of bounded treewidth and bounded vertex degree. <\/jats:p>","DOI":"10.1142\/s0129054120500069","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T09:17:18Z","timestamp":1583745438000},"page":"253-273","source":"Crossref","is-referenced-by-count":2,"title":["Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree"],"prefix":"10.1142","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9763-797X","authenticated-orcid":false,"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[{"name":"Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6832-0102","authenticated-orcid":false,"given":"Avraham A.","family":"Melkman","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, 84105, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1596-901X","authenticated-orcid":false,"given":"Takeyuki","family":"Tamura","sequence":"additional","affiliation":[{"name":"Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji, Kyoto 611-0011, Japan"}]}],"member":"219","published-online":{"date-parts":[[2020,3,6]]},"reference":[{"key":"S0129054120500069BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.007"},{"key":"S0129054120500069BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.07.010"},{"key":"S0129054120500069BIB003","doi-asserted-by":"publisher","DOI":"10.1109\/AICCSA.2007.370907"},{"key":"S0129054120500069BIB004","first-page":"1488","volume":"76","author":"Akutsu T.","year":"1993","journal-title":"IEICE Trans. Fundamentals"},{"key":"S0129054120500069BIB005","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35261-4_18"},{"key":"S0129054120500069BIB006","doi-asserted-by":"publisher","DOI":"10.3390\/a6010119"},{"key":"S0129054120500069BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00026-N"},{"key":"S0129054120500069BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/11847250_22"},{"key":"S0129054120500069BIB009","first-page":"684","volume-title":"Proc. 47th ACM Symp. Theory of Computing","author":"Babai L.","year":"2016"},{"key":"S0129054120500069BIB010","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808746"},{"key":"S0129054120500069BIB011","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00090"},{"key":"S0129054120500069BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/2151171.2151181"},{"key":"S0129054120500069BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"S0129054120500069BIB014","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"S0129054120500069BIB015","first-page":"213","volume":"77","author":"Duesbury E.","year":"2017","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"S0129054120500069BIB016","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"S0129054120500069BIB017","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"volume-title":"Computers and Intractability","year":"1979","author":"Garey M. R.","key":"S0129054120500069BIB018"},{"key":"S0129054120500069BIB019","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.01.003"},{"key":"S0129054120500069BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2018.03.007"},{"key":"S0129054120500069BIB021","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.002"},{"issue":"4","key":"S0129054120500069BIB022","first-page":"S-4","volume":"7","author":"Huang X.","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"S0129054120500069BIB023","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12340-0_28"},{"key":"S0129054120500069BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00286-3"},{"key":"S0129054120500069BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2017.07.012"},{"key":"S0129054120500069BIB026","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"S0129054120500069BIB027","first-page":"542","volume-title":"Proc. 31st Symposium on Theoretical Aspects of Computer Science","author":"Marx D.","year":"2014"},{"key":"S0129054120500069BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"key":"S0129054120500069BIB029","first-page":"226","volume":"51","author":"Nicholson V.","year":"1987","journal-title":"Stud. Phys. Theoret. Chem."},{"key":"S0129054120500069BIB030","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021271615909"},{"key":"S0129054120500069BIB031","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-013-9335-0"},{"key":"S0129054120500069BIB032","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1993.1027"},{"key":"S0129054120500069BIB033","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(00)00048-0"},{"key":"S0129054120500069BIB034","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90133-5"},{"key":"S0129054120500069BIB035","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87477-5_39"},{"key":"S0129054120500069BIB036","doi-asserted-by":"publisher","DOI":"10.2307\/2371086"},{"key":"S0129054120500069BIB037","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.06.019"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120500069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T09:17:41Z","timestamp":1583745461000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120500069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":37,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["10.1142\/S0129054120500069"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120500069","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2020,2]]}}}