{"entities":{"Q2026337":{"pageid":2037079,"ns":120,"title":"Item:Q2026337","lastrevid":57702573,"modified":"2026-03-31T23:52:08Z","type":"item","id":"Q2026337","labels":{"en":{"language":"en","value":"Maximum independent sets near the upper bound"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7349658"}},"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":"Q2026337$F6019FE6-D22A-43F9-81CA-557A0DCBA657","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"80f5bbf4f7eea0f0ca2abbf4f6ebc27d1fcedefa","datavalue":{"value":{"text":"Maximum independent sets near the upper bound","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2026337$F30B5114-A9EE-4B28-A3D3-1D57DDB8761F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55ba42da19dceacbb68520d3ec952f96bb62a68e","datavalue":{"value":"1473.05232","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$1E88A547-B0E7-4060-8878-245D7BB1A254","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b09124aade2f9a2d1dad9d1d88ddbbb2bdabd00","datavalue":{"value":{"entity-type":"item","numeric-id":228794,"id":"Q228794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$13995685-4847-4A49-A899-2175BB640685","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$3F0F867D-B335-4952-9A7B-7E792E829FD4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca67a9bc9689c1756b57e5ad5a0134b4d60900ad","datavalue":{"value":{"time":"+2021-05-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2026337$64B7CAFF-95ED-4C8C-8215-33A7A84AD64D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a2789a7b5fb09566fbcf3b6aba432b0f335e2ba9","datavalue":{"value":"https://arxiv.org/abs/1709.02475","type":"string"},"datatype":"url"},"type":"statement","id":"Q2026337$2A7254AD-E9F3-4714-93B0-48A75156D34F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d317c5a3acda87c74c2fc3e934165113e7027f3","datavalue":{"value":"An independent set of a graph \\(G\\) is a set of vertices where no two vertices are adjacent. The independence number is the size of a maximum independent set in the graph and is denoted by \\(\\alpha(G)\\).  Let us recall the following upper bound for \\(\\alpha(G)\\):  Theorem. Let \\(G\\) be a graph of order \\(n\\) and size \\(m\\). Then \\[\\alpha(G)\\leq p:=\\lfloor \\frac{1}{2}+\\sqrt{\\frac{1}{4}+n^2-n-2m}\\rfloor.\\]  The author considers independent sets near the above upper bound and proved the following result:  Theorem. There exists an algorithm with time complexity \\(O(n^2)\\) that, given as an input a graph \\(G\\) of order \\(n\\), size \\(m\\), \\(p:=\\lfloor \\frac{1}{2}+\\sqrt{\\frac{1}{4}+n^2-n-2m}\\rfloor\\) and an integer \\(k\\geq 0\\) with \\(p\\geq2k+1\\), returns an induced subgraph \\(G_{p,k}\\) of \\(G\\) with \\(n_0\\leq p+2k+1\\) vertices such that \\(\\alpha(G) \\leq p-k\\) if and only if \\(\\alpha(G_{p,k})\\leq p-k.\\)  Furthermore, he shows that one can decide in \\(O(1.2738^{3k}+n^2)\\) time whether \\(\\alpha(G_{p,k})\\leq p-k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2026337$218DC558-0A37-4646-A544-FAF91FA6EFED","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3e5241478eb111c3d7b9249ceb02ff850b9ad819","datavalue":{"value":{"entity-type":"item","numeric-id":277497,"id":"Q277497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$B80759B5-BB2F-41DA-BEEF-E9C43232BEA0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$F3D8DDB9-0E35-4C1C-9A7D-FD1C899D3C7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$57A61B28-BFC4-49B1-9A2B-85FA28E7C266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$E58CF7D0-2FE2-49C7-87F3-41BCEB88B25B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f91260de395a314d46d1c34fd003c544b4793e2","datavalue":{"value":"7349658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$BEC34209-B033-4963-81AF-7A2BC20E60E2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232465a4b21b2442783eb000a1c43840a0e6c26c","datavalue":{"value":"maximum independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q2026337$AA8BDAA0-7EC8-43B9-B3D5-1826B9230F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2026337$8DF74859-120D-446C-A75F-28873F4A21E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2026337$4ADE442B-ECBA-4CEB-B531-03FA7A679F0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f1d787b6eef119573a9061a62e40d7b15583b76","datavalue":{"value":"fast parameter tractable","type":"string"},"datatype":"string"},"type":"statement","id":"Q2026337$A3301133-137A-4328-BDFB-7222D282A65B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13de80a47f7375b61eec61bb6fb737bcf857cc47","datavalue":{"value":"fpt-algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2026337$393A36D1-7AF8-4297-AB7B-238AD56AC42F","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":"Q2026337$2C1D823E-8CEA-492F-9BA9-BF90458F176C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3a232ef375e0e07523f039a33ad553597ea3eb5e","datavalue":{"value":"W2963358149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$F9447A72-8050-4BAA-9610-CC74AD3942F4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3614b07925bf11635f52dee1649c0e1683b8b46a","datavalue":{"value":{"entity-type":"item","numeric-id":2346341,"id":"Q2346341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$B204C71B-4C83-4957-B1C3-18E6B5736A0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a92ab907df072bb20a1057061523b1fdda43679","datavalue":{"value":{"entity-type":"item","numeric-id":5782525,"id":"Q5782525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$052FF7DF-6247-4D3B-9FCB-D4591BD9F394","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"841afe5368ee90e97418d34d48b610064f41e432","datavalue":{"value":{"entity-type":"item","numeric-id":708228,"id":"Q708228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$4C11FB9F-F4D9-4328-BBFA-4A87F6FACF5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfeb6a659323d3b3be153da722b9186ac97dd120","datavalue":{"value":{"entity-type":"item","numeric-id":4636626,"id":"Q4636626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$DF7E1F97-D839-4EFF-AE2D-2DE0375F464C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$54D666EF-0628-4B65-A159-2D2FA0C2A52B","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":"Q2026337$38420F85-7522-4F0C-AEB9-FF20672FA958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ccf2ce6ffe932287a3e8f6d3b281b44fd4ad0eb","datavalue":{"value":{"entity-type":"item","numeric-id":4770411,"id":"Q4770411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$4F25228D-3BE7-45A0-866D-2A5970F7D4FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$E70797F4-DA8A-44C3-B625-33CE9E841E22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d28ad31cfa0964029ddd5e42793d4e65d4a53e2a","datavalue":{"value":{"entity-type":"item","numeric-id":4846683,"id":"Q4846683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$ED27550F-A642-439E-BD5A-8A78CA86C05A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d22e95cfb08114972c1514e26bef4d87d04d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5524918,"id":"Q5524918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2026337$D34CC90D-19DF-4076-8CB4-F8A854CDD8B7","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0424b73001c007abc69f84ad1c7c7ffd138610b9","datavalue":{"value":"Q129403042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$448D5C82-D236-440D-8EC4-C9C5B941EFAB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4315b4b743d8d6d878a12dd40f94ec1338190894","datavalue":{"value":"10.1016/J.DAM.2018.06.042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2026337$4476F841-E83E-40E8-AE24-82689959C5E0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c24a29e327c27dbf67ee97adafdd08c613070c4","datavalue":{"value":{"entity-type":"item","numeric-id":3777476,"id":"Q3777476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"609c1b9bebf732b0019cc473fc084d999b761210","datavalue":{"value":{"amount":"+0.8594006896018982","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":"Q2026337$4A9A8A0E-A01C-4946-BA9F-AB36C177F0E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"daecdb7d433a9028bbf185889a57bc8abc256d84","datavalue":{"value":{"entity-type":"item","numeric-id":1919180,"id":"Q1919180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78db84cdbbb3590c41f10c8f94051a87e46f9960","datavalue":{"value":{"amount":"+0.8222624063491821","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":"Q2026337$EFFC64AF-C0ED-4E0F-9E40-B21B2FBC4C46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b4fe9f27c219d7906f838f9121d27a7634cb62e","datavalue":{"value":{"entity-type":"item","numeric-id":4252376,"id":"Q4252376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80326377e613a593ad9c1044782a49dc81df389e","datavalue":{"value":{"amount":"+0.818615734577179","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":"Q2026337$E50CBC8E-F78D-41F8-871F-E047FEB2EAB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a979b2bc9a880db09c2c53d8f101750139cd8c5","datavalue":{"value":{"entity-type":"item","numeric-id":4873751,"id":"Q4873751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80326377e613a593ad9c1044782a49dc81df389e","datavalue":{"value":{"amount":"+0.818615734577179","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":"Q2026337$F5F00208-9868-4825-B016-45866E4D9DE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23f9710170281e2f38f0021bc2e94ec5894fa9f1","datavalue":{"value":{"entity-type":"item","numeric-id":2872097,"id":"Q2872097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"810e4f83a8105abf94e95deb4fa5570c905b303f","datavalue":{"value":{"amount":"+0.815121054649353","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":"Q2026337$610E1E42-E3DD-46FA-AFC3-040684B6E6C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2026337","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2026337"}}}}}