{"entities":{"Q2094884":{"pageid":2105627,"ns":120,"title":"Item:Q2094884","lastrevid":57725274,"modified":"2026-04-01T02:57:27Z","type":"item","id":"Q2094884","labels":{"en":{"language":"en","value":"Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7613671"}},"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":"Q2094884$4C3E643A-BE69-490C-AB5C-5883EA58F579","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5575103ed00d0ed79ee14516c8b1a01b28e82eff","datavalue":{"value":{"text":"Feedback vertex sets in (directed) graphs of bounded degeneracy or treewidth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2094884$186DAE77-9487-46CC-9BCF-CF5E0EB20AF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5128fe9706050ca62155e14192250d740c98faf2","datavalue":{"value":"1503.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$9E33D52E-47F3-451B-9290-2A175F69586A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a7f07863b59aa928d53ab6e5f26fdc46d44f966","datavalue":{"value":"10.37236/10914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$8C833E20-0068-4B7B-903B-FC5F01F236FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cda44dfe2f9ee366a391219133826b36ee03b4ad","datavalue":{"value":{"entity-type":"item","numeric-id":251890,"id":"Q251890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$1069F1DC-BACD-469E-A5F6-7BB90873DB87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c89df3b0068bb2d8e663045f7551d1ad01884ca","datavalue":{"value":{"entity-type":"item","numeric-id":2032973,"id":"Q2032973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$3A8BEFA4-D4D6-4604-BCF2-65E6348075D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1551e327938d61dbbdf3f2fa2adcad20184199e0","datavalue":{"value":{"entity-type":"item","numeric-id":477353,"id":"Q477353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$95111150-983E-45E4-BD38-D26E2A07A4AE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$5AE239AE-F1DF-4E74-8DA3-29F3479BFC27","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41c2d4b2b9eee3d1d4724659108ff6928154d594","datavalue":{"value":{"time":"+2022-11-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":"Q2094884$57EA9EAD-091E-48B9-9ED7-712759C023CA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43ffa4e7d7c8446ab7a4a56abe66438ef127fdb7","datavalue":{"value":"https://arxiv.org/abs/2111.14986","type":"string"},"datatype":"url"},"type":"statement","id":"Q2094884$A5094CCE-60FE-44DF-9981-4DC652141D13","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"32550cbde8e228c6c695dd9bae5c5531e8d63c94","datavalue":{"value":"Summary: We study the minimum size \\(f\\) of a feedback vertex set in directed and undirected \\(n\\)-vertex graphs of given degeneracy or treewidth. In the undirected setting the bound \\(\\frac{k-1}{k+1}n\\) is known to be tight for graphs with bounded treewidth \\(k\\) or bounded odd degeneracy \\(k\\). We show that neither of the easy upper and lower bounds \\(\\frac{k-1}{k+1}n\\) and \\(\\frac{k}{k+2}n\\) can be exact for the case of even degeneracy. More precisely, for even degeneracy \\(k\\) we prove that \\(f < \\frac{k}{k+2}n\\) and for every \\(\\epsilon>0\\), there exists a \\(k\\)-degenerate graph for which \\(f\\geqslant \\frac{3k-2}{3k+4}n -\\epsilon\\).  For directed graphs of bounded degeneracy \\(k\\), we prove that \\(f\\leqslant\\frac{k-1}{k+1}n\\) and that this inequality is strict when \\(k\\) is odd. For directed graphs of bounded treewidth \\(k\\geqslant 2\\), we show that \\(f \\leqslant \\frac{k}{k+3}n\\) and for every \\(\\epsilon>0\\), there exists a \\(k\\)-degenerate graph for which \\(f\\geqslant \\frac{k-2\\lfloor\\log_2(k)\\rfloor}{k+1}n -\\epsilon\\). Further, we provide several constructions of low degeneracy or treewidth and large \\(f\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094884$046B53F3-DF48-4BDF-BCFE-38006A0F2C75","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$BCC0F8E1-48A9-4072-8C24-B52ECFAAAB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$26872449-5F8F-4A31-9D6F-0CBA2039803B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$D0E7F1BB-6E8D-41DD-B09F-B81F30D8034D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63b0cb929a4d05bf6543bfd0733c773c3a79aedc","datavalue":{"value":"7613671","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$9039789A-10A8-4708-AF04-0A07A296D1F1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f52dd19283d0a086cca1b0dd1533b225238396b","datavalue":{"value":"planar directed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094884$1D50CC8D-A5C6-4132-A820-AA6BDE00638B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6d49cfb1e4c39c6acbfd1e6a37751a0100c25d4","datavalue":{"value":"tournaments","type":"string"},"datatype":"string"},"type":"statement","id":"Q2094884$6B4A081C-FE4A-4086-97B1-DB9002B41376","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":"Q2094884$D19D591B-2F8B-479C-9A16-9A7198737FE6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ebf37ac1ece035e2da5618be79b7cbd935ae441e","datavalue":{"value":"W3216545571","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$E6B6B4FB-523D-4995-9EFD-4FEA6CBB5BEF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"378cb32fedebbb04e30f06b7e1bef560c306dd6d","datavalue":{"value":{"entity-type":"item","numeric-id":4137202,"id":"Q4137202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$4898D4FD-4F34-4380-9E87-EE530D6953EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"277ab160b8ab1137d44aea43c72e269c6a4f23f3","datavalue":{"value":{"entity-type":"item","numeric-id":300250,"id":"Q300250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$8332BA44-1DCD-421D-A564-D4BA658F2DED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43f123cbca9423ba4f7f7523eb537f1b0cdc3662","datavalue":{"value":{"entity-type":"item","numeric-id":5509547,"id":"Q5509547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$A55A5DC2-010D-4765-8A77-6211E84E9118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2341643324efaaa5f443197afb822fa4c6eff2f","datavalue":{"value":{"entity-type":"item","numeric-id":528978,"id":"Q528978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$B173775D-A7C6-496E-84D8-500A322B2BBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d47036a59ad31a455fcef56e3f4d2c3850e326ce","datavalue":{"value":{"entity-type":"item","numeric-id":1853123,"id":"Q1853123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$6A866359-818B-4BC6-B03F-78D5AA28E86A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$BDF177EE-91D4-4D28-A159-E44DC6D787B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25514d1df94b84a9d5fc0a7905e100be0df37f3f","datavalue":{"value":{"entity-type":"item","numeric-id":5272647,"id":"Q5272647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$517B9EFB-64C4-4AC4-96FF-E6ACE81E72D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7633ab79a68cbf6dad6890f208f4b3f7e5bef87","datavalue":{"value":{"entity-type":"item","numeric-id":1222168,"id":"Q1222168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$2B1D79B7-C7BE-49F2-8B73-AA09507F2BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b26688ad0a58910eda60809a6e3cf7d71438c0ea","datavalue":{"value":{"entity-type":"item","numeric-id":5361236,"id":"Q5361236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$78B84E7F-A03A-4B26-8F03-07B81CA8782F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06baaffbb3d94e24bd93cccb267bc9746e3c4b55","datavalue":{"value":{"entity-type":"item","numeric-id":5163505,"id":"Q5163505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$AA3E64C8-B571-48CB-81B7-69DEDE8B2C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f89ad6be3bfa69ace8aee41bf8c6a413eb8d71e","datavalue":{"value":{"entity-type":"item","numeric-id":1343231,"id":"Q1343231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$4033A6DF-9E02-4EFF-B5E4-7CE343537C90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"002e0b9aafed84a85558eee4b75a83327708d2b4","datavalue":{"value":{"entity-type":"item","numeric-id":1393032,"id":"Q1393032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$39DE16FC-018B-4F74-A3B9-CC8D58DA834C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39a230d5cb89c5252302ce7ea3be1b5351601147","datavalue":{"value":{"entity-type":"item","numeric-id":3263757,"id":"Q3263757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2094884$0C0B0157-B231-47A7-828A-E4A5FB9EA241","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"18433351f2fdb51a6051e62a722c07f9629977a5","datavalue":{"value":"bafybeifhz5kkk435ekr3ipdxhazsiwyu5sk5mgmjkxdky6a5iowkyha3oq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2094884$9CBC8FE8-43EA-4A32-BBC7-4915FFB93897","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24feecdefd769c20a028547057501d219ea2479f","datavalue":{"value":{"entity-type":"item","numeric-id":300250,"id":"Q300250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b05237143ca8d1af533a6d1b5a067608f31c506","datavalue":{"value":{"amount":"+0.8119048476219177","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":"Q2094884$90610429-0DE4-4D35-9A33-E6CD0B4B3278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a428d338a20b53f67988b2cc8bc821815200590","datavalue":{"value":{"entity-type":"item","numeric-id":4425958,"id":"Q4425958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"589f256c6defb18e2afe0f50c7b5e331a21e3a08","datavalue":{"value":{"amount":"+0.7748562693595886","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":"Q2094884$D473DFAD-C2AB-4D11-9FDD-148EEADC4F06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6334d80bdfa5378c6d7c7e8fde9c8375fb66e791","datavalue":{"value":{"entity-type":"item","numeric-id":1853123,"id":"Q1853123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"589f256c6defb18e2afe0f50c7b5e331a21e3a08","datavalue":{"value":{"amount":"+0.7748562693595886","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":"Q2094884$9B14D23E-3DD8-4EFA-8952-D53938060EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e156dd1e4b679dfee07e52108842c2055210a91","datavalue":{"value":{"entity-type":"item","numeric-id":1627154,"id":"Q1627154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86e101fde2ef457e3755e72207fd5c2cd0fce9c3","datavalue":{"value":{"amount":"+0.768151581287384","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":"Q2094884$93091B09-BD8E-460B-A849-4C977BD01236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5d785995a5042ff44b9276019fcd68ffec0b6a3","datavalue":{"value":{"entity-type":"item","numeric-id":2944523,"id":"Q2944523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64e617257f17427cd8cc3436a7b82b364ab7f37a","datavalue":{"value":{"amount":"+0.7659821510314941","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":"Q2094884$F462D428-B606-40CC-82FE-079FD3313436","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":"Q2094884$3D54F4B0-51CD-4B6B-9370-ADDFC1B62441","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2094884","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2094884"}}}}}