{"entities":{"Q2354017":{"pageid":2364760,"ns":120,"title":"Item:Q2354017","lastrevid":72581973,"modified":"2026-04-14T05:54:28Z","type":"item","id":"Q2354017","labels":{"en":{"language":"en","value":"Hitting all maximal independent sets of a bipartite graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6457219"}},"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":"Q2354017$ADAC7C54-2D67-4019-87AC-9773893D597F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"31406e717f91adb60dd8021a5309894629fd3ce5","datavalue":{"value":{"text":"Hitting all maximal independent sets of a bipartite graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2354017$FE310636-C85B-4E03-9DBC-E182DB6FBCCC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22b2110cf06f55a8998186a1a20369a301d4bbfc","datavalue":{"value":"1328.05139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$C47715D6-C17D-4000-8B58-8F51E3963B56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8726a15dc299cd4173f24acc61812735416bfa6","datavalue":{"value":{"entity-type":"item","numeric-id":364845,"id":"Q364845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$4F77B2DA-837F-4459-930D-C9F13189DE85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bb1d48e699dcbd07426b1c3ee3831813e5c5d7b0","datavalue":{"value":{"entity-type":"item","numeric-id":412238,"id":"Q412238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$53B5F033-7348-46E2-BC9B-D9A8568F6E7D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$2F2F3747-6548-4AED-A0A8-131DC8D00E0E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9969939bb103ca6857dea96cf377517e2479ab0a","datavalue":{"value":{"time":"+2015-07-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2354017$4D55FE85-6697-4D1D-8EA8-F31F5F7BE008","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"316da31023201cc9ce9adb32116d6073ec9c8e9c","datavalue":{"value":"https://arxiv.org/abs/1208.5589","type":"string"},"datatype":"url"},"type":"statement","id":"Q2354017$B885EADA-5ACC-4994-AF94-B121721DF31D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5a1ee50d048201417584d80a3d5969aa2a58d1ae","datavalue":{"value":"A maximal independent set in a graph is a subset of pairwise nonadjacent vertices that is maximal with respect to inclusion. A vertex subset of a graph \\(G\\) meeting all maximal independent sets of \\(G\\) is called a transversal of \\(G\\).  The main result of this paper is: Given a bipartite graph \\(G\\) and a positive integer \\(k\\), it is \\(\\sum_{2}^P\\)-complete to decide whether \\(G\\) has a transversal of size at most \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354017$D446D4CC-0E95-4A31-8A8C-CA7E81EBE1B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$B80DC89C-3D5E-44F6-8E3E-830AD1411504","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$B40DBFF0-D060-48A6-8048-95B5BA4BE566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$8B44A254-092F-4793-96FE-7A72305B6554","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0cee1cfc7294c3c953819c5c7c4e84956b23e83d","datavalue":{"value":"6457219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$7870BBBA-BA3F-490E-8FA1-0255FA8FF0A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ae5cad662cee9457a0e88de5ca640ccabb9ba00","datavalue":{"value":"maximal independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354017$141CF86D-2DBB-4B33-B406-222A18D08398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d39367e9a6054750bde0ee6e234c86a51879458e","datavalue":{"value":"clique transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354017$A2976B31-ABA9-4B18-9DD2-CC6BF57170AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c916e647d73dc3b9cd5b7782460a55bc34994156","datavalue":{"value":"fiber in posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354017$CC6D3419-5335-4188-B952-F2E730AC9510","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"03fbe7b2f6f1b6ae6ddb79e37e418388d814131d","datavalue":{"value":{"entity-type":"item","numeric-id":630191,"id":"Q630191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$FC66813C-FBA1-4A72-A316-FC3B0EAD4D9F","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":"Q2354017$108C3FD6-D978-4B05-B461-F154747DCC26","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6420d231db3648b46296b8a17f9a51c724300b6f","datavalue":{"value":"W3105919819","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$B4BA0D13-A9D0-4E16-8C11-5A6323C5EED3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d8c3c9a4b968f607553357d3b0f2f035ae1da1d","datavalue":{"value":{"entity-type":"item","numeric-id":1971220,"id":"Q1971220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$477C3287-6605-4550-A002-0872EE04FE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"556f2ea55bf879ccd5a1be2224f02ea17a5b72e6","datavalue":{"value":{"entity-type":"item","numeric-id":1584423,"id":"Q1584423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$39593663-CA5A-4C0C-9AD6-1554D437D0F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d974179afb3a4da3b4f27eeba0d09358afcfa28","datavalue":{"value":{"entity-type":"item","numeric-id":810533,"id":"Q810533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$8C7A5C10-B4E8-4A3B-B3D9-F2DC0986DC00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5b82f7b1a4073bc4c9f0009d3df8c0e8eb8773b","datavalue":{"value":{"entity-type":"item","numeric-id":4652597,"id":"Q4652597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$CD62AAE8-08CF-45FB-ACEC-539CC7F9C314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9761a0cc19f897a3746927037f04b504c7b4310a","datavalue":{"value":{"entity-type":"item","numeric-id":1177956,"id":"Q1177956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$04EAB06F-1AAE-4B4A-871A-97A6AED58084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4276199f337e80f22cd0a037a4918c76805dbf80","datavalue":{"value":{"entity-type":"item","numeric-id":1176381,"id":"Q1176381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$FA078C58-B14C-4A43-AF7D-6B65678E473F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fd81e604511c142841127d04f6d5d036af9350d","datavalue":{"value":{"entity-type":"item","numeric-id":940841,"id":"Q940841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$F48EDDE1-EC04-48A2-838A-CB15B42338B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5890ae5a283b4e8716396304a346cee90071e82","datavalue":{"value":{"entity-type":"item","numeric-id":1854773,"id":"Q1854773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$67F52CFA-4B9D-48BE-A5D5-8E141908D3EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70c937326045597237bc5e22805f0b091613787c","datavalue":{"value":{"entity-type":"item","numeric-id":1201260,"id":"Q1201260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$55463837-0D3E-4527-AF41-8EA7EA5CCF30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ab91af9300c03108c83f175294005fece9bfeff","datavalue":{"value":{"entity-type":"item","numeric-id":4153610,"id":"Q4153610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$2A022B4C-76B2-4EA0-8FA9-FE9A30FBE188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff78e10b473763a5802f01c541b98c94ab07e690","datavalue":{"value":{"entity-type":"item","numeric-id":4806592,"id":"Q4806592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$8F83796F-5E75-4F64-81CD-6E7327EAD901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d79cf878065e69a3a1a7c2f5f1f92399af5cbd34","datavalue":{"value":{"entity-type":"item","numeric-id":1098863,"id":"Q1098863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$A9773DD0-2653-4A25-B74B-936160B5ACB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fdaf7fd3e706499baaed393a3be2992bedc4ed17","datavalue":{"value":{"entity-type":"item","numeric-id":551168,"id":"Q551168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$61624399-7D13-4B97-9A70-A888759564D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$D1452734-4D98-4111-A287-146B1FFB1E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$8DD06364-7935-4CF7-A68F-48F680176875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00b79ce7beb3596052714e5eb40fbfabb9a3ecac","datavalue":{"value":{"entity-type":"item","numeric-id":1174130,"id":"Q1174130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$13BE80E5-5C1E-4EC1-ABA3-21E24F2B624A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3065df023fcb2411980df376c6fc4777f5d291a5","datavalue":{"value":{"entity-type":"item","numeric-id":1241440,"id":"Q1241440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354017$D2D0CCA1-332C-460D-BCAD-73BE18FDC663","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c6b9ec1581a8a2bf4be0a4f5266a105386b14fb5","datavalue":{"value":"10.1007/S00453-013-9847-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354017$BA3A99E7-0FA5-4C20-A8F2-F533B1312410","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34fb472b2edfce0b30afe15ea5f779496eb35043","datavalue":{"value":{"entity-type":"item","numeric-id":3137766,"id":"Q3137766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a61b826f3176434a2539a32c33db0efc17bfd46d","datavalue":{"value":{"amount":"+0.7926792502403259","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":"Q2354017$6352D283-DE78-49AD-9036-B136A861DA21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5bc54987cd5c99fbb31a9a339961c5ca287698c","datavalue":{"value":{"entity-type":"item","numeric-id":607358,"id":"Q607358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a61b826f3176434a2539a32c33db0efc17bfd46d","datavalue":{"value":{"amount":"+0.7926792502403259","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":"Q2354017$F5CD8204-A838-44A1-8A6A-525B96E39D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"860d9b8e08c7baec367c7f54b1b8b263696e7c53","datavalue":{"value":{"entity-type":"item","numeric-id":2717906,"id":"Q2717906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fb75e0b4f995e8eb4f8cc0fb30850f93b01ed52","datavalue":{"value":{"amount":"+0.7833439707756042","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":"Q2354017$0B74F84C-0E81-4A18-826C-7293CF29FAAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"784c68f2ba8d5fc31cddab31372956fd89faa048","datavalue":{"value":{"entity-type":"item","numeric-id":1847371,"id":"Q1847371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cfecbac42c31dbb880a678bcf9fa65b4473f3f1","datavalue":{"value":{"amount":"+0.7827000617980957","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":"Q2354017$C19B0779-D388-4ED3-960B-8C7E6B4BFD7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"884996bb3c710830ce84622aab27e31355b808c0","datavalue":{"value":{"entity-type":"item","numeric-id":4304413,"id":"Q4304413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bbd934333d11b4eb0962c1ab037d0085d4e8415","datavalue":{"value":{"amount":"+0.7646957635879517","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":"Q2354017$F30CC818-80EB-4D11-9E87-B7E3B084D967","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Hitting all maximal independent sets of a bipartite graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Hitting_all_maximal_independent_sets_of_a_bipartite_graph"}}}}}