{"entities":{"Q5918307":{"pageid":8048912,"ns":120,"title":"Item:Q5918307","lastrevid":57648264,"modified":"2026-03-31T19:01:00Z","type":"item","id":"Q5918307","labels":{"en":{"language":"en","value":"Stable divisorial gonality is in NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7363128"}},"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":"Q5918307$301CC7A4-5694-4631-AF6E-34332CCBCDBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3e37f57ac12d86a07bec12e54b3a0a446ceefe06","datavalue":{"value":{"text":"Stable divisorial gonality is in NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5918307$38E56C16-FB41-4FE8-BBA3-F59F676D4D8C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d1c995d2d8c44795a3528ffa2fe85b627a29df6","datavalue":{"value":"1477.68204","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$9DB7AB63-FC11-4924-9E18-E2ADA1B5BE46","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"926e613762971a9014a8b1ed071772bdcf0a0812","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$619B4F7F-D104-4982-8692-A49E119C832F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"232b3c8cb60e678de899aa1cf191c2433c8eade6","datavalue":{"value":{"entity-type":"item","numeric-id":820547,"id":"Q820547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$FB92D921-21D8-466E-AB34-8F5EB931A1C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a4b673d2d1101ae2711e41ca3ee6d63b023456c","datavalue":{"value":{"entity-type":"item","numeric-id":1628691,"id":"Q1628691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$BC109006-E6A6-4ECA-8A34-04E4C0786328","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b559743f011d61696dff04b2ecd3408df2541e49","datavalue":{"value":{"entity-type":"item","numeric-id":169698,"id":"Q169698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$60AA32C6-48E5-4C10-B2E9-B387D896325C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"98ccd645dac13aee75d2844835d2fad35a9a43cb","datavalue":{"value":{"time":"+2021-06-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5918307$C49FD793-E6FB-4CAD-8FD4-69E5F5BDA0DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"026b12738ba848c30e972d6e2d22dbf6f30d04c6","datavalue":{"value":"Divisorial gonality and stable divisorial gonality have definitions in terms of a chip-firing game. In this chip-firing game, played on a connected multigraph \\(G = (V,E)\\), each vertex has a number of chips. When we fire a vertex \\(v\\in V\\), we move a chip from vertex \\(v\\) over each edge with \\(v\\) as endpoint. Vertex \\(v\\) has its number of chips decreased by the degree of \\(v\\), and each neighbor \\(u\\) of \\(v\\) has its number of chips increased by the number of edges from \\(v\\) to \\(u\\). The divisorial gonality of a connected graph \\(G\\) is defined as the minimum number of chips in an initial assignment of chips (called divisor) such that for each vertex \\(v\\in V\\), there is a sequence of firing moves resulting in at least one chip on \\(v\\) and a non-negative number of chips on the other vertices. The stable divisorial gonality of a graph is a variant of the divisorial gonality, which is the minimum of the divisorial gonality over all subdivisions of a graph.  In this paper the authors prove that deciding whether a given connected graph has stable divisorial gonality at most a given integer \\(k\\) belongs to the class NP. Combined with the result that (stable) divisorial gonality is NP-hard in [\\textit{D. Gijswijt} et al., Discrete Appl. Math. 287, 134--149 (2020; Zbl 1450.05088)], the authors obtain that stable divisorial gonality is NP-complete. The proof consists of a partial certificate that can be verified by solving an Integer Linear Programming instance. As a corollary, they have that the total number of subdivisions needed for minimum stable divisorial gonality of a graph with \\(m\\) edges is bounded by \\(m^{O(mn)}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918307$817D7225-ABC8-4562-A0CF-1CA81C022FA2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4241d06a5ad40c81408acdad1396e5c461f38e81","datavalue":{"value":{"entity-type":"item","numeric-id":831023,"id":"Q831023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$BD9FF542-AA09-4841-B257-D583E0F13479","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$850C12DC-4C85-4F5A-B83D-266839043FFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$98600BF3-8736-45FD-BC75-6541292F9876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$0A541DD1-E91E-4655-899C-B3C7DE146482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$90C038DD-DA90-4B14-AA43-F1B8C1D2BAE2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"36a9bfbaf18fed38bfd18fcb461f9a4fcfaa0488","datavalue":{"value":"7363128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$96F7E4BD-D0F9-4B15-9390-AE5A95F1479F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918307$B290EB00-5D09-478B-800E-EA6F21C9CDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d3e2c5cdbb9bf737c4fa7ac78971f831677d8a1d","datavalue":{"value":"graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918307$69CFBE88-728F-4E94-8731-1E3ABB720784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bfbc1a6aa8a283e03f6762e2e72172268b66170","datavalue":{"value":"gonality","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918307$A60540B3-8EDE-42E5-A336-7101C32042F9","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":"Q5918307$DF6768A1-3FEF-4651-9551-E43B5795BB29","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d2e8f5d6a3889e1815589a825eb651d688d6901","datavalue":{"value":"https://doi.org/10.1007/s00224-020-10019-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q5918307$71E5C27D-458F-4592-94D7-58744A594343","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f32ab488a42207076811c3e24f904c10af04205d","datavalue":{"value":"W3111297488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$6F794665-F756-47BA-A60D-9A32C8C41672","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f510072c7e0b651673dfdefc1b104d7be8dc00e9","datavalue":{"value":{"entity-type":"item","numeric-id":5918977,"id":"Q5918977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$2FBEDDBD-9E5C-4A01-9F5C-1CB1FDC48CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c854ac3cdec572ade97ae094b8098a59289a4487","datavalue":{"value":{"entity-type":"item","numeric-id":4584275,"id":"Q4584275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$3B7901EE-C241-4781-8836-8B362F1E07D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c31ac6340b8992fae4a91f1ded457ca9a8578f71","datavalue":{"value":{"entity-type":"item","numeric-id":2383008,"id":"Q2383008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$F806834B-1A27-4433-9060-D7D5F07C3096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a634cf9766b989e04f31307e91fce4d6d782043","datavalue":{"value":{"entity-type":"item","numeric-id":1005880,"id":"Q1005880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$CA1A6906-A35B-4B12-BF3F-C22B5CCCF785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8df05b5e5a5f4617ba8be23feef5f40cf874c165","datavalue":{"value":{"entity-type":"item","numeric-id":5246007,"id":"Q5246007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$53969F47-9103-466B-A0E9-2B80F714367E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bc66d008d2c0d09811bf559b5cbcd2504db96be","datavalue":{"value":{"entity-type":"item","numeric-id":2255277,"id":"Q2255277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$300941D6-68AE-4918-A0E0-28B95A576ABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e73ceb80b00f543babac70632e61117134a96362","datavalue":{"value":{"entity-type":"item","numeric-id":2200865,"id":"Q2200865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$04E5883F-4B40-4F75-A9B9-1EEB8092103C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8717d03c53d2c609b7f8df0119f32ed700b7528","datavalue":{"value":{"entity-type":"item","numeric-id":5919531,"id":"Q5919531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$B9341884-2D43-4D55-93F7-9E9AEC3EDFDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f86d107bfe28ac75765be5d16c6b3ba2ccfb269","datavalue":{"value":{"entity-type":"item","numeric-id":2004086,"id":"Q2004086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$4119B670-1492-4BC2-8A65-A708018EB664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff0b1adf1bd3f78f82d6ef197f464289bf7c4ee8","datavalue":{"value":{"entity-type":"item","numeric-id":1758511,"id":"Q1758511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$2F44503D-E6A2-4A3A-A691-517381C8494C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$785ADD3A-5BB2-4D10-BFE9-759949F9736F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99b4eae7493d8f6c982d7549031f59a2b3902483","datavalue":{"value":{"entity-type":"item","numeric-id":3922169,"id":"Q3922169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$F76923C3-A84C-4035-9E31-177859100108","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e25395b3279667bed2fb9468d223947ac11f2a1f","datavalue":{"value":"10.1007/S00224-020-10019-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918307$CF9D17B6-9534-4FD2-83E7-BB2E5DCE696F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b042748e2de3afcb9ea43f7bd520dc55198674ae","datavalue":{"value":{"entity-type":"item","numeric-id":5918977,"id":"Q5918977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"428c2a533c91db293e6c15f3698fa25b43516ee6","datavalue":{"value":{"amount":"+0.9541698694229126","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":"Q5918307$7230D6A3-FDE3-4DE9-9B93-4CE9329F2A9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ca2622dd33377624fd35c890e30a67ca5f65c91","datavalue":{"value":{"entity-type":"item","numeric-id":2004086,"id":"Q2004086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d6450d52e2866d135e154a20de1c100157eb705","datavalue":{"value":{"amount":"+0.846682071685791","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":"Q5918307$E642218A-0F27-475A-828F-537CFBA9AAF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d0ac0c2e75b9e1bcf6cde0b4ae88da2453e275e2","datavalue":{"value":{"entity-type":"item","numeric-id":6098103,"id":"Q6098103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83db7c735308bcdb3e5b31cfae5510455ec6dae3","datavalue":{"value":{"amount":"+0.8166964650154114","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":"Q5918307$69278A62-FF43-479A-9E5E-A8D002B48307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e253b6048749d7875db8fa4b828c099a07150cf","datavalue":{"value":{"entity-type":"item","numeric-id":5226830,"id":"Q5226830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aa21f98305e5c2988f98668e32645d0704699c5","datavalue":{"value":{"amount":"+0.8103054761886597","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":"Q5918307$327E0EFE-1197-403A-8785-099DC2688499","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62a7a058de774ea91125c2cb904d11b5562d6289","datavalue":{"value":{"entity-type":"item","numeric-id":2354726,"id":"Q2354726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc2d59da6e8c78f260be11e7c833ba6d9fa91c19","datavalue":{"value":{"amount":"+0.7790759801864624","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":"Q5918307$31942D5A-202D-4B7E-9964-BAB014133713","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918307$B734D084-23EB-497C-ADA9-B2D182286FEA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5918307","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5918307"}}}}}