{"entities":{"Q1179032":{"pageid":1189781,"ns":120,"title":"Item:Q1179032","lastrevid":66512883,"modified":"2026-04-12T10:34:56Z","type":"item","id":"Q1179032","labels":{"en":{"language":"en","value":"NP-completeness of graph decomposition problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 23778"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$255FD531-6EA4-4E3D-87C7-FA383D2D4B04","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fe2f229bf32ee68141ee7b01ade6e03887a76fc6","datavalue":{"value":{"text":"NP-completeness of graph decomposition problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179032$C28CC81C-B98F-4494-8BCD-7D2792A08269","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a5a1363148173ede34bc819d201d3040f8817a92","datavalue":{"value":"0741.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179032$5084D178-3DD7-46FF-9FEC-EF9F1FE124C9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9aab70296b849dfd96bed1db86624232e18ee838","datavalue":{"value":"10.1016/0885-064X(91)90006-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179032$21E02AA8-4E7C-4588-967B-80D3F8441995","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa62924fb1814642b9b89d5358876c982dc8ef1e","datavalue":{"value":{"entity-type":"item","numeric-id":878693,"id":"Q878693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$F8373439-3170-4041-815E-65A771CA948C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6528a033086d689548cd6b323306dad1d6651466","datavalue":{"value":{"entity-type":"item","numeric-id":286767,"id":"Q286767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$A6A73D66-87C3-42EA-B561-1EA9BE7A5539","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f728e963338f0590fef2609026707340c65ee9d2","datavalue":{"value":{"entity-type":"item","numeric-id":162057,"id":"Q162057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$E6D828D9-6B48-4071-8495-0C5F7788B17A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1179032$9A6CDDE3-6D32-463F-B184-AC492D68DC65","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"95803f5189ef30c775bfee72bc8db51c8d5bcc85","datavalue":{"value":"For a fixed graph \\(H\\), the \\(H\\)-decomposition problem is as follows: Can a given (input) graph \\(G\\) be decomposed as an edge disjoint union of subgraphs, all of which are isomorphic to \\(H\\)?   \\textit{I. Holyer} [SIAM J. Comput. 10, 797-808 (1981; Zbl 0468.68069)] conjectured that the \\(H\\)-decomposition problem is \\(NP\\)-complete whenever \\(H\\) has at least 3 edges and is connected. Holyer's conjecture had been proved for \\(H=K_ m\\) (a complete graph), \\(P_ m\\) (a path) and \\(C_ m\\) (a cycle).   The main result of this paper is: If \\(H\\) is a connected graph with at least three edges and \\(H\\) has a vertex \\(v\\) such that all the vertices adjacent to \\(v\\), except at most one of them, are of degree one in \\(H\\), then the \\(H\\)-decomposition problem is \\(NP\\)-complete.   From this it follows that Holyer's conjecture is true for a family of graphs which includes all trees with at least three edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179032$4B812043-C8D2-4F6E-A79F-F6547321FDE9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0dfbdb0929ddc22bcd5bd1c182b95d3875d4d630","datavalue":{"value":{"entity-type":"item","numeric-id":1164054,"id":"Q1164054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$31504AAE-D429-49C4-BCF0-2E8BFF3938D5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179032$EEC5769D-378A-4670-94FB-2F246B1C0072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179032$80FF54D8-09B2-4BB5-9284-AAAC9290BFB2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"11bd559489c93eb231457f0828a82cd4209ba635","datavalue":{"value":"23778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179032$18C43220-FF08-45ED-ADEE-294E11F6AB91","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34cd38c0980e2a4569ba72d6a3552f7b9cbe6b67","datavalue":{"value":"\\(NP\\)-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179032$819364D4-328F-425B-ADD7-C2B1AC84AC9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee46e2c6a42a74803d50f6329947494bb4a53f6","datavalue":{"value":"graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179032$8C024DB3-6213-433B-8648-E40BFD1F54E9","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$E3055EA4-4F37-471F-BF44-72E0313A5D23","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e42d0f5ab49275e4c0794702ef3fa6b4fe3b134","datavalue":{"value":{"entity-type":"item","numeric-id":790841,"id":"Q790841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$589C3F0C-40AE-458B-AC0C-33C52C0DD06D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"380a307b17ee314fe3714f228b3df36c866a091e","datavalue":{"value":{"entity-type":"item","numeric-id":4097307,"id":"Q4097307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$BEF52E73-0DD9-4E03-A9BD-376959F752A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6115ed0ad53d4a46da343f030c2abb614bc7aed8","datavalue":{"value":{"entity-type":"item","numeric-id":3919753,"id":"Q3919753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$2113F802-D65A-4385-8B6A-B1E7074091B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"767177c9c2beae2d8abc0a60a160c198d5edad64","datavalue":{"value":{"entity-type":"item","numeric-id":3901534,"id":"Q3901534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$F4F4BB7C-15A6-4F01-AF8A-0A9CAE5D2C87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18dea8e782b03ec96dd715526409df91ff4ef53a","datavalue":{"value":{"entity-type":"item","numeric-id":3741644,"id":"Q3741644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$1CDF251E-B453-40BA-902C-C67DADBB6C99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$AC55267C-EFF4-4346-9915-0FE20A8E6E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff5e201c2b579b8c70d76c6408c175e8ca744357","datavalue":{"value":{"entity-type":"item","numeric-id":3922182,"id":"Q3922182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$8794AC31-D6A8-46D6-9F30-6A3EA0648E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b14233efbc23e31889365df721ca3ba294a25b","datavalue":{"value":{"entity-type":"item","numeric-id":5402563,"id":"Q5402563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179032$EEF385EF-F87B-4434-BFEB-AA9A0298F4D4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c8fb2238e59b4f565cb23d298202daf96789e06c","datavalue":{"value":"https://doi.org/10.1016/0885-064x(91)90006-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179032$9F811A3C-2D9B-4E68-ACE8-C388E45CC0B6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0ad9ef83e07ce4cd0f2951b1b6cfd37e8e0c0df1","datavalue":{"value":"W2066714987","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179032$DCC90299-FFEC-4B73-8E8D-257CDEB86AAD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"870d74d1ef7774cbaa95eb9015b00c25f0491408","datavalue":{"value":{"entity-type":"item","numeric-id":4376161,"id":"Q4376161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2b800dd529a618229e0adf045e52b125262819c","datavalue":{"value":{"amount":"+0.946280837059021","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179032$A642F506-59A7-4588-9864-1E49202636D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b205b97e038ee4d5d30a2196f03bafc5025ab69","datavalue":{"value":{"entity-type":"item","numeric-id":1024436,"id":"Q1024436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27bf2e6a5f57cb12f4d4b2e00c3e3086da9cc95c","datavalue":{"value":{"amount":"+0.877070426940918","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179032$48F3171E-8547-40C1-94D2-7E6B38D7A5C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2b052d009f0bc086a473c7c86104b63f82fbd26","datavalue":{"value":{"entity-type":"item","numeric-id":1354723,"id":"Q1354723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"244bc0d22b33e174efa2b3f030db3b77701e36dd","datavalue":{"value":{"amount":"+0.8403650522232056","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179032$63A24DE4-09BE-41C1-82BD-68037BBDB6F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"354904d9b199b0f465d400fbc983759a6beeed19","datavalue":{"value":{"entity-type":"item","numeric-id":1045169,"id":"Q1045169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0deb1a322a56c154c02baf2e710d728fc1082796","datavalue":{"value":{"amount":"+0.8351118564605713","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179032$6DD4C458-95BD-4E75-9C34-41A562FCC0F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"NP-completeness of graph decomposition problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/NP-completeness_of_graph_decomposition_problems"}}}}}