{"entities":{"Q1205723":{"pageid":1216472,"ns":120,"title":"Item:Q1205723","lastrevid":69884748,"modified":"2026-04-13T10:59:39Z","type":"item","id":"Q1205723","labels":{"en":{"language":"en","value":"The complexity of finding arborescences in hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 148039"}},"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":"Q1205723$EEBBF2FF-771E-4CB2-AA84-271A49E47A2D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c0b1ace697ec17b39a55ef2b8ce7af000ad81dea","datavalue":{"value":{"text":"The complexity of finding arborescences in hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1205723$6E12AF2F-3434-4A9E-9B83-06D46EC8E103","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"70c6d1319bce4720dda96b212d7da6e5752be9f6","datavalue":{"value":"0760.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$CC642E76-1473-467C-98FD-418BFBF1784C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e03dda95d29042eed4e25e831827ff42943fea9","datavalue":{"value":"10.1016/0020-0190(92)90057-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$A2FFE384-E880-4AC1-A073-D1940D23A12C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$EBC36517-DB35-4880-91E6-10AF399ACB2A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8604b2a4c08e4f5e10819826d060da1f7baa01ac","datavalue":{"value":{"time":"+1993-04-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1205723$08691786-93C2-400C-87FA-E9C2743053ED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fa53cc92d75a0c2e53fdc505379957b901547710","datavalue":{"value":"We prove that ASP is NP-complete even if all edges in \\(H\\) are of cardinality three. This is the strongest possible result, since the case where all edges are of cardinality two is solvable in polynomial time (this case can be represented as the intersection of two matroids, see [\\textit{A. Frank}, J. Algorithms 2, 328-336 (1981; Zbl 0484.05025)]). The fastest known algorithm for this special case is due to \\textit{R. E. Tarjan} [Networks 7, 25-35 (1977; Zbl 0379.90100)] and runs in \\(O(\\min\\{m\\log n,n^ 2\\})\\) time, where \\(n\\) denotes the number of vertices and \\(m\\) denotes the number of edges of the graph.   Further we prove that the corresponding problem in undirected graphs is solvable in polynomial time by the standard Greedy algorithm, since the underlying structure forms a matroid.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1205723$C8ADEB72-A6C0-44B1-9D45-505D494D99D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$4EDEC54E-C578-4D00-B90E-7FC40B6D7CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$2FAEF374-EC8E-40D3-AACD-04A47EA3FCEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$EC73CEC8-DACF-4236-8F45-AFCB033AF24A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3bd19baeb2949ca3259b903eac378581d37dc16a","datavalue":{"value":"148039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$73D1CF7F-9B43-4DC7-A539-BA6F1F7760BD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c100c034119ae696d8307e517f4dd0ec76149d4","datavalue":{"value":"arborescence subhypergraph problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1205723$B642C1CF-D45E-477F-AE7B-92ECD5A30B7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4a99c5b7728e1965ef01019ed8fae6583a2f22e4","datavalue":{"value":{"entity-type":"item","numeric-id":170010,"id":"Q170010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$56154D28-9D81-4A98-9A2D-A8C23AEDC0AC","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":"Q1205723$A3463C74-2365-49BB-BC33-8C93D60ACA13","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82cb38bcda505db0ef6ed9a96334383496db8dc6","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90057-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1205723$07D9D918-A390-4C90-8290-4AB181E527AF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ceffc5e8f3e8eb0a259a905aef82a4a128e7bba5","datavalue":{"value":"W2155171773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1205723$AE75883A-F60F-41DA-A932-C37ABAEAF7EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"163439bf15333d78c5f11564941a2c37f94759b7","datavalue":{"value":{"entity-type":"item","numeric-id":3942972,"id":"Q3942972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$F6E0C54D-4450-4C32-B120-5C12B3449AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$6A7084D8-B3C5-4539-9DF4-B3BA9B23871F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$AB1CEEE3-13B5-42B2-B94E-96F64A28161C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7598deaa60e33f46db1320dc1b85a677389b314","datavalue":{"value":{"entity-type":"item","numeric-id":4158841,"id":"Q4158841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$1A2A8322-DF58-47AB-801E-0EB6A7EC320C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1205723$51376895-4ABA-4163-905F-D78E145E29F1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73383379772714e0d12158739d75eeaa94d041cb","datavalue":{"value":{"entity-type":"item","numeric-id":6155599,"id":"Q6155599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"253aa784d604410476039725fb7c001a5a31d994","datavalue":{"value":{"amount":"+0.7683465480804443","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":"Q1205723$E1B865C0-26E1-48A0-8ECC-23EB042FADC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86cd4a4a862ccaab3a3f4632d175bbb85e127837","datavalue":{"value":{"entity-type":"item","numeric-id":1336639,"id":"Q1336639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2869d02082fc299d4d597dc539cbca60f6f89107","datavalue":{"value":{"amount":"+0.7587177157402039","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":"Q1205723$EFBECEB8-715A-47B0-B5F1-B1B4EEC3E766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"278200bf54133faf142fe8f547d12919ad74fd3c","datavalue":{"value":{"entity-type":"item","numeric-id":5101431,"id":"Q5101431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a72501fb5480d2036ab7df80e4cf0c7009fcf1e","datavalue":{"value":{"amount":"+0.7577497959136963","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":"Q1205723$CE47B321-5984-4745-954B-ECEEBFEC5553","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of finding arborescences in hypergraphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_finding_arborescences_in_hypergraphs"}}}}}