{"created":"2023-05-15T12:00:49.237641+00:00","id":7781,"links":{},"metadata":{"_buckets":{"deposit":"67a03c87-ca07-4e43-b87d-b9318c48a8e1"},"_deposit":{"created_by":3,"id":"7781","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"7781"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00007781","sets":["8:9"]},"author_link":["6037","34129","34131","34128","34132"],"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2013-01-10","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"99","bibliographicPageStart":"88","bibliographicVolumeNumber":"27","bibliographic_titles":[{"bibliographic_title":"Journal of Combinatorial Optimization"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"The paper studies a generalization of the INDEPENDENT SET problem (IS for short). A distance-d independent set for an integer d≥2 in an unweighted graph G=(V,E) is a subset S⊆V of vertices such that for any pair of vertices u,v∈S, the distance between u and v is at least d in G. Given an unweighted graph G and a positive integer k, the DISTANCE-d INDEPENDENT SET problem (D d IS for short) is to decide whether G contains a distance-d independent set S such that |S|≥k. D2IS is identical to the original IS. Thus D2IS is NP-complete even for planar graphs, but it is in P for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D d IS, its maximization version MaxD d IS, and its parameterized version ParaD d IS(k), where the parameter is the size of the distance-d independent set: (1) We first prove that for any ε>0 and any fixed integer d≥3, it is NP-hard to approximate MaxD d IS to within a factor of n1/2−ε for bipartite graphs of n vertices, and for any fixed integer d≥3, ParaD d IS(k) is W[1]-hard for bipartite graphs. Then, (2) we prove that for every fixed integer d≥3, D d IS remains NP-complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D d IS can be solved in polynomial time for any even d≥2, whereas D d IS is NP-complete for any odd d≥3. Also, we show the hardness of approximation of MaxD d IS and the W[1]-hardness of ParaD d IS(k) on chordal graphs for any odd d≥3.","subitem_description_type":"Abstract"}]},"item_21_description_60":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"subitem_description":"Journal Article","subitem_description_type":"Other"}]},"item_21_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"34131","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Eto,  H."}]},{"nameIdentifiers":[{"nameIdentifier":"34132","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Guo,  F."}]},{"affiliations":[{"affiliationNames":[{"affiliationName":"","lang":"ja"}],"nameIdentifiers":[]}],"familyNames":[{"familyName":"Miyano","familyNameLang":"en"},{"familyName":"宮野","familyNameLang":"ja"},{"familyName":"ミヤノ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Eiji","givenNameLang":"en"},{"givenName":"英次","givenNameLang":"ja"},{"givenName":"エイジ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"6037","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"10284548","nameIdentifierScheme":"e-Rad","nameIdentifierURI":"https://nrid.nii.ac.jp/ja/nrid/1000010284548"},{"nameIdentifier":"6603649200","nameIdentifierScheme":"Scopus著者ID","nameIdentifierURI":"https://www.scopus.com/authid/detail.uri?authorId=6603649200"},{"nameIdentifier":"0000-0002-4260-7818","nameIdentifierScheme":"ORCiD","nameIdentifierURI":"https://orcid.org/0000-0002-4260-7818"},{"nameIdentifier":"233","nameIdentifierScheme":"九工大研究者情報","nameIdentifierURI":"https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}],"names":[{"name":"Miyano, Eiji","nameLang":"en"},{"name":"宮野, 英次","nameLang":"ja"},{"name":"ミヤノ, エイジ","nameLang":"ja-Kana"}]}]},"item_21_link_62":{"attribute_name":"研究者情報","attribute_value_mlt":[{"subitem_link_url":"https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}]},"item_21_publisher_7":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Springer"}]},"item_21_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1007/s10878-012-9594-4","subitem_relation_type_select":"DOI"}}]},"item_21_rights_13":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright (c) Springer Science+Business Media New York 2013. This is a post-peer-review, pre-copyedit version of an article published in Journal of Combinatorial Optimization. The final authenticated version is available online at: https://doi.org/10.1007/s10878-012-9594-4."}]},"item_21_select_59":{"attribute_name":"査読の有無","attribute_value_mlt":[{"subitem_select_item":"yes"}]},"item_21_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1573-2886","subitem_source_identifier_type":"ISSN"},{"subitem_source_identifier":"1382-6905","subitem_source_identifier_type":"ISSN"}]},"item_21_text_28":{"attribute_name":"論文ID（連携）","attribute_value_mlt":[{"subitem_text_value":"10347752"}]},"item_21_text_36":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Kyushu Institute of Technology"},{"subitem_text_value":"Kyushu Institute of Technology"},{"subitem_text_value":"Kyushu Institute of Technology"}]},"item_21_text_63":{"attribute_name":"連携ID","attribute_value_mlt":[{"subitem_text_value":"10664"}]},"item_21_version_type_58":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Eto,  Hiroshi"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Guo,  Fengrui"}],"nameIdentifiers":[{}]},{"creatorAffiliations":[{"affiliationNameIdentifiers":[],"affiliationNames":[{"affiliationName":""}]}],"creatorNames":[{"creatorName":"Miyano, Eiji","creatorNameLang":"en"},{"creatorName":"宮野, 英次","creatorNameLang":"ja"},{"creatorName":"ミヤノ, エイジ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{},{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2022-10-03"}],"displaytype":"detail","filename":"10347752.pdf","filesize":[{"value":"161.3 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"10347752.pdf","url":"https://kyutech.repo.nii.ac.jp/record/7781/files/10347752.pdf"},"version_id":"d6f5a1ae-03e5-4cdb-9227-47ec92deab1f"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Distance-d independent set","subitem_subject_scheme":"Other"},{"subitem_subject":"Bipartite graphs","subitem_subject_scheme":"Other"},{"subitem_subject":"Chordal graphs","subitem_subject_scheme":"Other"},{"subitem_subject":"Computational complexity","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Distance-d independent set problems for bipartite and chordal graphs","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Distance-d independent set problems for bipartite and chordal graphs"}]},"item_type_id":"21","owner":"3","path":["9"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-10-03"},"publish_date":"2022-10-03","publish_status":"0","recid":"7781","relation_version_is_last":true,"title":["Distance-d independent set problems for bipartite and chordal graphs"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2024-04-02T08:39:14.902057+00:00"}