{"entities":{"Q1841907":{"pageid":1852649,"ns":120,"title":"Item:Q1841907","lastrevid":47574703,"modified":"2026-01-02T03:04:57Z","type":"item","id":"Q1841907","labels":{"en":{"language":"en","value":"On the hardness of computing maximum self-reduction sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1565943"}},"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":"Q1841907$BB3F53E2-0D4F-4703-B53E-0A9A3BDF4FC2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1661b123576b3d6e5540d62b181463a998971b59","datavalue":{"value":{"text":"On the hardness of computing maximum self-reduction sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1841907$F189667D-0DFD-4F78-9D30-95A9F6E9EC98","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d0d1f30dbe572cf3c6b8dbdb26636f908f9b0db","datavalue":{"value":"0982.05099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841907$92918095-FCD6-4C5B-9EE2-EFA31E10A808","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"74bbea174c6e7b4abd5afefc20ba4ff52255533f","datavalue":{"value":"10.1016/S0012-365X(00)00132-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841907$72198747-DB34-4F12-AC3C-C0E6F3381C5E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"410a532419e08754d7bb51e62d2575c4941404e8","datavalue":{"value":{"entity-type":"item","numeric-id":284389,"id":"Q284389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841907$F40F4E81-0541-43CC-8CB0-E10EC6002A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9fa0cb0ae58eb274bc2cac17aed8b2bc4cdfa441","datavalue":{"value":{"entity-type":"item","numeric-id":876696,"id":"Q876696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841907$087B7808-EC71-4D1C-9B2F-DC2D3BE96999","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841907$D65A630C-2F94-48D2-BDB0-B38D0F56907F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c13d1740a28716c4c5bfcac03995e635a2c76533","datavalue":{"value":{"time":"+2002-04-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1841907$6716D2A5-2A5A-4E19-8923-3F7C2DC7FD2D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d600595a20d477f68193f5ccde65842baeeae202","datavalue":{"value":"Various combinatorial problems on graphs can be approached by reducing the size of the graph according to certain rules (i.e., reducing complete subgraphs to one vertex).   Here the authors show that computing maximum reduction sequences for the operation ``two-pair reduction'' [see, i.e., \\textit{J. Fonlupt} and \\textit{J. P. Uhry}, Ann. Discrete Math. 16, 83-95 (1982; Zbl 0502.05023)] is NP-hard. Thus there is no benefit for the solution of combinatorial graph problems using this reduction type. They also extend this result to other types and larger sets of self-reduction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841907$6F0FAA90-6069-432F-BF45-60CA2E0FD092","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841907$E4994E0D-5485-4F4D-B959-FC3552988201","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841907$368937FA-9C80-4880-BA4B-0BC53EB54B1B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2cbaacf69a6634d57d8dabca5e02f85a95439943","datavalue":{"value":"1565943","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841907$0322C12C-3CDA-4410-BEB0-A1CC49D496BE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51b336acc1a2a9943c1b7597223af4ac6fdba76c","datavalue":{"value":"reduction sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841907$496BDAA0-8C89-4713-9B1D-9FAA19E88AAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27815bdc3e09d30949c98717e9b0e55e78349b75","datavalue":{"value":"self-reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1841907$4ACB4FAD-DCB4-491A-B8A7-788DBAE8B46D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5bf98c249556a3cbdf1ccaf58ec85cdce76ec514","datavalue":{"value":{"entity-type":"item","numeric-id":593214,"id":"Q593214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1841907$2684D00A-C236-49F6-9707-7FAF50EB7725","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":"Q1841907$3F1433F3-1AF3-4B47-A94B-1C47318C39C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4a77808ce264fe69e7dbd0a9648e33421e1c7f96","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00132-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1841907$A7564F10-0C18-460C-A310-01C7ED671674","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"65a045813f2d0577fba72580a7d0fc35002220c2","datavalue":{"value":"W2013505915","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1841907$B8909ED1-77FB-466F-B750-64CC40E4DFB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"040ec92cc214599ecdf38d6bd02ff3927f501733","datavalue":{"value":{"entity-type":"item","numeric-id":1669583,"id":"Q1669583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e26506679825cb3c67ee4e4e0a48199d86c8807","datavalue":{"value":{"amount":"+0.7799800634384155","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":"Q1841907$02B8EA8F-4241-4458-BF74-FF9C22BC2A27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe51adcb058a3a54ac022e3d6f7edbd8b5bfbd50","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18ba5b7c2c2396bb59ff19206794b47a42baf2b7","datavalue":{"value":{"amount":"+0.7587019205093384","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":"Q1841907$0C10F2D3-3369-4982-B346-64CA26F8202A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0017b9fea4eb88c34afc22dc99d57919130a95","datavalue":{"value":{"entity-type":"item","numeric-id":876697,"id":"Q876697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dc87088836302d7f7ea23333a1041dc7f4c6af2","datavalue":{"value":{"amount":"+0.7486699819564819","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":"Q1841907$B2A30219-2E9C-44F5-AF74-0C371B5ABCF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5728a1f7ee92a18c99a7aece97b0864c87b41f75","datavalue":{"value":{"entity-type":"item","numeric-id":5402566,"id":"Q5402566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"355f409394ecd2bd9a533bc293f988a0e8cdf169","datavalue":{"value":{"amount":"+0.7333955764770508","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":"Q1841907$615CCCF8-26B6-4063-A5CC-2B7C7B986029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4242ccb97fdc9da97495446a2b017c95339ab1a2","datavalue":{"value":{"entity-type":"item","numeric-id":3364155,"id":"Q3364155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b19402c6d8916bb52d00e052bf7e96484943bc9f","datavalue":{"value":{"amount":"+0.7323544025421143","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":"Q1841907$4E076C5F-6C7E-4946-97EE-91D0302709F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1841907","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1841907"}}}}}