{"entities":{"Q6163958":{"pageid":13298839,"ns":120,"title":"Item:Q6163958","lastrevid":58735698,"modified":"2026-04-06T12:55:27Z","type":"item","id":"Q6163958","labels":{"en":{"language":"en","value":"Cutting a tree with subgraph complementation is hard, except for some small trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7719334"}},"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":"Q6163958$855B15F5-80F2-4BB4-BBCE-82C77F59F17F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ff334d3bdcf8168806570ada90bdf50bc9352f4","datavalue":{"value":{"text":"Cutting a tree with subgraph complementation is hard, except for some small trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6163958$D4E4184E-551D-4108-B739-741EEADDFBAD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b663bd93054abff69cf918bb992efd55471234ba","datavalue":{"value":"10.1007/978-3-031-20624-5_1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6163958$9650FED4-9B22-4093-A036-1D6C6863C1C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cf1e91608ab4b480cef685caed2619a389a0245c","datavalue":{"value":{"entity-type":"item","numeric-id":2088582,"id":"Q2088582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$D4262E0B-B36F-4151-B8DF-DE599FAADE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7862a9b2d78ec36b9e96182e4eadb463622062b","datavalue":{"value":{"entity-type":"item","numeric-id":2088584,"id":"Q2088584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$F9CD87F4-2BFF-4449-8CD4-7FE6E62AF8F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96fc28243a4801bf2a9230b7e379fdc040471ad5","datavalue":{"value":{"entity-type":"item","numeric-id":1679220,"id":"Q1679220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$CE6DD4EA-8257-47F4-83DB-DA0F3C84C8B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ed6eb3bb547819e3671e8638e4d0ffafa7c7d45d","datavalue":{"value":{"entity-type":"item","numeric-id":777286,"id":"Q777286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$8095A8E2-E8D4-4A39-A1A9-4F42050B2F55","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"eaaf386aa056e2ce7e654c5274f8a683c6ed004d","datavalue":{"value":{"entity-type":"item","numeric-id":6108997,"id":"Q6108997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$987983BA-435A-4CF9-809B-7BB4A5BB4804","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2a737b362c9cc4a7577c7886e9ed43c21a3fff2e","datavalue":{"value":{"time":"+2023-07-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":"Q6163958$F7E58DEF-62C2-4730-896E-4A14BAA068BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d2125bd00637f86ffa5dfcbf2125677ba29fae3c","datavalue":{"value":"https://arxiv.org/abs/2202.13620","type":"string"},"datatype":"url"},"type":"statement","id":"Q6163958$CB7719CB-7A92-4BC9-9EB5-54D7F5DA1149","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6163958$01BA6BB1-DA8F-4F97-9816-9ECCF23F5E7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1397c7d07b55282862d4db12cbe94becf8137559","datavalue":{"value":"68Rxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6163958$049E8C95-70A6-41D8-9D6B-95735AAD0124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6163958$2DA166C0-6C04-4152-A3DA-E6D0546A143D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1d00b07d20ad26a4142a8f7b43e94264cc7388ca","datavalue":{"value":"7719334","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6163958$E8D53A9C-3DB1-4B84-82E7-EACE6E3D78FE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"829503689288ff1aa9447a3a11c59c49ed70eb73","datavalue":{"value":"subgraph complementation","type":"string"},"datatype":"string"},"type":"statement","id":"Q6163958$0F8E389D-651C-4788-8E05-787AC3964034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"409040ae64a601c4a24d439a8d81c49c0ca673ab","datavalue":{"value":"graph modification","type":"string"},"datatype":"string"},"type":"statement","id":"Q6163958$3FAB1FC1-9F62-46BF-B824-D7C7D94C15AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q6163958$4E0A14D4-B826-4DBC-85BF-B26E8940B0FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6450ebe2b4b217baa53a9e96eaad22c40c7ffb0f","datavalue":{"value":"paw","type":"string"},"datatype":"string"},"type":"statement","id":"Q6163958$1C82A543-3848-4930-B789-63AE393840F4","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":"Q6163958$A2ADCE80-1577-4120-9CFF-1B1E046F25AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c763b7d2a15a1b7a772998da011c41f9861f939","datavalue":{"value":"W4312273856","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6163958$12049F9C-C343-42A5-865F-DC49718F3F4C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"54c40f5e287ce342e31e29db5c0eab02e99343e0","datavalue":{"value":{"entity-type":"item","numeric-id":3416248,"id":"Q3416248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$7B0CE10C-0A3F-44AD-AB17-B880909574E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$AA672D98-8B58-4530-AAC0-5528D1CE5E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39b851e406aa7071875e5e8a730aed77089dbc45","datavalue":{"value":{"entity-type":"item","numeric-id":1108293,"id":"Q1108293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$BF5A5621-BEAB-402B-A51A-00F67498F41A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$F25E9381-4731-432C-8D42-209C023C448D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8807a77b16516cbd9e09421a89f1b5dfabfc8c7f","datavalue":{"value":{"entity-type":"item","numeric-id":5384003,"id":"Q5384003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$40F9C419-7850-4C2D-9A20-89FA2ACDF3D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd2a411b16fc2c459d186cca895548cbb291c1a4","datavalue":{"value":{"entity-type":"item","numeric-id":5236261,"id":"Q5236261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$4CC8FA66-6755-43A6-9CCE-D7A083E3816E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e98793f595a582da1d2eb499de73fd52aa4a8e45","datavalue":{"value":{"entity-type":"item","numeric-id":5346539,"id":"Q5346539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$497D7B08-90E4-48E2-ADA2-46EEA3EA0C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c95488d33c7f5f660efc9a0540767728ccb24d3","datavalue":{"value":{"entity-type":"item","numeric-id":3921260,"id":"Q3921260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$9D2F9333-0C84-40C9-A727-DCABCAFE5951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76da9d7282ed72cc2ef9d5860c040c5d6873ce63","datavalue":{"value":{"entity-type":"item","numeric-id":2672430,"id":"Q2672430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$D7426FDF-AE6C-4FD7-9B0D-29C02EDEA721","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"032a2cccd6aa7b286288c39dbb930b5a9fce8e89","datavalue":{"value":{"entity-type":"item","numeric-id":1034612,"id":"Q1034612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$53E04BEB-E2E7-408A-AD9E-F4FD30753780","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beaf048e99659f9d0cafa996ba6ee77900af81ea","datavalue":{"value":{"entity-type":"item","numeric-id":2839211,"id":"Q2839211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$14703123-BED1-4E5D-AAFE-E05A49FCD568","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c0af54c4697424ffe5938847e3cc68a7991f9ac","datavalue":{"value":{"entity-type":"item","numeric-id":3801094,"id":"Q3801094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$65C8F7C3-9DCA-468A-A8E2-F1A7693D6442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"576b1f09854bc416b20f72b33a63f446b660512a","datavalue":{"value":{"entity-type":"item","numeric-id":713321,"id":"Q713321"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$1C39F271-7786-472A-A2F1-47205F4C5F81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b7ee278fe84aec01cca081cf7a688c807b681e5","datavalue":{"value":{"entity-type":"item","numeric-id":1885821,"id":"Q1885821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$DEA267AA-D9FD-45CD-9037-ABD2698DEA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a082668d45b4afcec0f7cb60775db4394c61b9e","datavalue":{"value":{"entity-type":"item","numeric-id":5417832,"id":"Q5417832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$C62E9990-94BB-4111-B5FC-291A475F1514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd40ba865a32761ce6589d238d690d54ced42d2c","datavalue":{"value":{"entity-type":"item","numeric-id":4814092,"id":"Q4814092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$D894CDB5-B053-40CA-A95B-37F01E3A93DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0415202f47c71bb01fdf9479aecfe1915250d582","datavalue":{"value":{"entity-type":"item","numeric-id":1924124,"id":"Q1924124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$27430EE0-6624-47E9-92C4-A10C30FFEF7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d808437cb510bfa585c7ac5cf20e7af7c5ba691f","datavalue":{"value":{"entity-type":"item","numeric-id":5967036,"id":"Q5967036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$BA4E3ABC-9478-4176-A3C2-E9E72F937A68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61a140f9a2efc67b1206bc93ee19916ba6fbf127","datavalue":{"value":{"entity-type":"item","numeric-id":4027169,"id":"Q4027169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$66CCBA7F-22A6-40F2-BB7D-FC7C6EB98F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bf20013ec0c32b335e2f3913209aa2d312718ef","datavalue":{"value":{"entity-type":"item","numeric-id":4437501,"id":"Q4437501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$E81378DF-68E8-45CE-9FCC-D90591F4F3A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20ff5ef87f4d0f1e1d1b8b1ce53a692e3004bf6e","datavalue":{"value":{"entity-type":"item","numeric-id":2802953,"id":"Q2802953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$BDF00C26-8375-4639-A329-C0944442A8EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a92824326b8e40198c48b71f41dfe819ccd0e563","datavalue":{"value":{"entity-type":"item","numeric-id":2071824,"id":"Q2071824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$77BC5ADD-7AF3-415B-8598-9CCE1250081E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8b294c6454a568279c59d8850b30d828f419a06","datavalue":{"value":{"entity-type":"item","numeric-id":1662097,"id":"Q1662097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$1045316A-50D5-4CFF-82CB-E950BA0B8B10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92a5e640c42040ebfa82f411097dc49eb438d720","datavalue":{"value":{"entity-type":"item","numeric-id":2343091,"id":"Q2343091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$1A8182B4-926F-4787-AF4D-7F850021D455","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b29828782073de2e9e9f0ead79546257ffe0627d","datavalue":{"value":{"entity-type":"item","numeric-id":1759680,"id":"Q1759680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$72D61052-AF6D-4C7C-A5EC-6E73D65D0392","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccd44e9b0d4019f33196a547e3557d1ab1dcf736","datavalue":{"value":{"entity-type":"item","numeric-id":2072105,"id":"Q2072105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$75A0D25A-AB76-4BD7-BA6C-AAB7207B6527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5e83afa0ef524338709b23fb5d4a8edc825a7da","datavalue":{"value":{"entity-type":"item","numeric-id":1949740,"id":"Q1949740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$0461534C-7F6A-4C0A-B4CF-CAD638EB0198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e8dffe87ec1ce651d955cd049fb39e7d89d48d5","datavalue":{"value":{"entity-type":"item","numeric-id":5919117,"id":"Q5919117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$A6ED19E2-97E6-4148-A849-CB8BEC28DB07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14451dfc28958e1dc95b63792df195a4fcb756f0","datavalue":{"value":{"entity-type":"item","numeric-id":6089654,"id":"Q6089654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$FF8B3370-2D49-4131-BE91-DDEDA85F576B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f05850b775d4250d97170eb0a8be844ff72ea76f","datavalue":{"value":{"entity-type":"item","numeric-id":4973877,"id":"Q4973877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$2E13BF98-896A-4C24-B177-B305F9E531F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9001c5ea90a954557f0ac10357c47c6f8c94b6a","datavalue":{"value":{"entity-type":"item","numeric-id":967317,"id":"Q967317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$1153FBD3-BF6F-418C-9402-8B84073DA217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765044b0ce99a6042eca6d96fc360d165408c7e3","datavalue":{"value":{"entity-type":"item","numeric-id":2182091,"id":"Q2182091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$EECCD996-237B-4E3C-93A9-BDE5742163B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"601c1dbd4a78012ab0eb9856d6a927b0319bb830","datavalue":{"value":{"entity-type":"item","numeric-id":2121776,"id":"Q2121776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$B48FFDE1-5403-4E38-8B18-CCB0ADA4FEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08cc9cdd9999a46859ae4f667ab34baac016718b","datavalue":{"value":{"entity-type":"item","numeric-id":5502162,"id":"Q5502162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6163958$C1BB4908-B94F-4C82-BB66-F4EAEAF66099","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6163958","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6163958"}}}}}