{"entities":{"Q6162136":{"pageid":13297017,"ns":120,"title":"Item:Q6162136","lastrevid":56768259,"modified":"2026-03-23T13:15:53Z","type":"item","id":"Q6162136","labels":{"en":{"language":"en","value":"The complexity of the matroid homomorphism problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7696233"}},"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":"Q6162136$AD1AA81B-690A-4644-B6AB-E65E4B90958D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a12c40f302cd1277672f1f1397229fa6648a1357","datavalue":{"value":{"text":"The complexity of the matroid homomorphism problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6162136$44DC8FC9-8F18-47AE-8CE8-A712A1CAACE5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5dfeb7a1c07190ced2b2b3e85745b94497a80397","datavalue":{"value":"1516.05021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6162136$3E637B46-4253-4725-B65B-B18731CB4D58","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"528d2c869f0f635cadfd4691cc980e3b8100401e","datavalue":{"value":"10.37236/11119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6162136$B60B153B-0A79-4AD9-8198-475DB3CA8424","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c086df85f88746984b0998ec71109183b01ae0a","datavalue":{"value":{"entity-type":"item","numeric-id":5041744,"id":"Q5041744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$A18ADE08-9858-4E5A-9222-4628B90ABDF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f12dc72f15208b65ec16204ea2a0b0e80afa5c8","datavalue":{"value":{"entity-type":"item","numeric-id":6162134,"id":"Q6162134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$F502D3DC-DFC9-4071-A22F-661FA2C90D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"280e6535c8db61b4e0a84403c89c4573be71f8fc","datavalue":{"value":{"entity-type":"item","numeric-id":6162135,"id":"Q6162135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$4562C82B-C0BF-430A-A628-8E532FD57F58","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":"Q6162136$727D87D2-2588-4F67-B1F4-D245A373F4F3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b16353a59d462651b8369dc98a71ef493226d62e","datavalue":{"value":{"time":"+2023-06-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6162136$012C0476-10C4-4DF7-B4A2-9F8237747460","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"251bfaae44b6c724225258f5f32e5de05d28faf0","datavalue":{"value":"Summary: We show that for every binary matroid \\(N\\) there is a graph \\(D(N)\\) such that for the graphic matroid \\(M_G\\) of a graph \\(G\\), there is a matroid-homomorphism from \\(M_G\\) to \\(N\\) if and only if there is a graph-homomorphism from \\(G\\) to \\(D(N)\\). With this we prove a complexity dichotomy for the problem \\(\\mathrm{Hom}_{\\mathbb{M}}(N)\\) of deciding if a binary matroid \\(M\\) admits a homomorphism to \\(N\\). The problem is polynomial time solvable if \\(N\\) has a loop or has no circuits of odd length, and is otherwise NP-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6162136$B234E5E1-0BCF-40C4-A286-8916CC4F673C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6162136$1A3D5129-E162-4E51-9FDC-58D7CBA3262A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d9a4e87e0b277ee660224a228349fc9d12e578db","datavalue":{"value":"52B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6162136$E5C395B4-4F00-44B4-B3A8-A8E2191F5F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6162136$FE896E9E-B734-4B9F-8409-B2BFEA193849","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"adbc73b50a761db50ae08d0e3833441dff2550c0","datavalue":{"value":"7696233","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6162136$1BF2F889-54A6-4249-AAAB-EEF705B96238","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f55f661112f9d1215e8a059ec3d7084c2611c37","datavalue":{"value":"binary matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q6162136$DD20702E-20CB-4FDF-9636-5D4703BE25F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df9e51d04a883fe06a859ed8502fdac1c497139e","datavalue":{"value":"matroid homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q6162136$FAB19AD4-D511-489F-A136-B53D474C1C24","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":"Q6162136$F0D14324-4486-4FCD-9E25-7A60F2720A4A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"68864d66118cf96a4b4b2dce6d9af44f92ab96e0","datavalue":{"value":{"entity-type":"item","numeric-id":5389972,"id":"Q5389972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$8A86F31C-7073-405D-A4C1-3CC7F03905BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$602F71A4-D96E-4CDA-9184-564064979297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2cad0419316111f4f87da733ecde246b034fc01","datavalue":{"value":{"entity-type":"item","numeric-id":4798127,"id":"Q4798127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$89AE2316-8EDF-49D6-A5DE-B9550FA7D842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fec165abc7ade014841f417bcba31a647c17e0c7","datavalue":{"value":{"entity-type":"item","numeric-id":1100215,"id":"Q1100215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$9F2B52FE-E0EF-4669-8DA1-06A72FAA93E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"598edae1e935535edc199f734f519c3a8fe28f46","datavalue":{"value":{"entity-type":"item","numeric-id":3277098,"id":"Q3277098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$238E9BE1-5462-44A4-A23D-6FA405A8A7D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7320d954512806b28d25cf778aca07b71655a643","datavalue":{"value":{"entity-type":"item","numeric-id":4752593,"id":"Q4752593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$FB4DAC61-819E-4AA4-827F-982C4761487C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbf845399cfc2fa36cc448865f810566596b9d10","datavalue":{"value":{"entity-type":"item","numeric-id":5133982,"id":"Q5133982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6162136$DFF4DE23-F264-45EB-82D7-A7428353F5FD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d466b5f6fcbc733adc9fe7eb140e5c89d680071e","datavalue":{"value":{"entity-type":"item","numeric-id":1840660,"id":"Q1840660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e19f6113e502d31f3b7ae2a60fd363a282f8974d","datavalue":{"value":{"amount":"+0.7709437608718872","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":"Q6162136$D9497DA8-F870-443D-AF74-D7CBA46923A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7f1cea973e37d997cfb13fb05e92e4f673578c8","datavalue":{"value":{"entity-type":"item","numeric-id":1923593,"id":"Q1923593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e19f6113e502d31f3b7ae2a60fd363a282f8974d","datavalue":{"value":{"amount":"+0.7709437608718872","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":"Q6162136$536AE017-9F4F-4B49-A027-BEC766444BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b59d34f1b34e2f467c7d2ee855735c2ede76b8","datavalue":{"value":{"entity-type":"item","numeric-id":639843,"id":"Q639843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c838a44bbe8959788147a132e72374f76530af8a","datavalue":{"value":{"amount":"+0.7678623199462891","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":"Q6162136$313F3E4D-D91C-4005-A555-F09B88EC9855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a0fad1bf7f64417e8ef6878bc2c875e35df518b","datavalue":{"value":{"entity-type":"item","numeric-id":3392964,"id":"Q3392964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e9c86dbb91ae421e884349c6f58a27e30362c91","datavalue":{"value":{"amount":"+0.7675456404685974","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":"Q6162136$30794A04-6663-429A-A0A6-2F800189F8D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfbd3a17c8f119fffc038086479c2dc451253d82","datavalue":{"value":{"entity-type":"item","numeric-id":4878664,"id":"Q4878664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f1c5592ac04bba7d1cab6839d5fa9d9bfcb40ff","datavalue":{"value":{"amount":"+0.7620428204536438","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":"Q6162136$07D72EFB-FBC1-477B-8B18-68AC0D569953","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":"Q6162136$0205B0B1-BF3F-4D20-B4CA-A134E6122A8E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6162136","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6162136"}}}}}