{"entities":{"Q1736640":{"pageid":1747381,"ns":120,"title":"Item:Q1736640","lastrevid":56794968,"modified":"2026-03-23T15:17:20Z","type":"item","id":"Q1736640","labels":{"en":{"language":"en","value":"The parameterized complexity of the rainbow subgraph problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042237"}},"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":"Q1736640$9CD54A59-A241-448C-A943-9089D3C7A5F4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"99d5fa5dd4a57970d6f5fe01270b40c980456728","datavalue":{"value":{"text":"The parameterized complexity of the rainbow subgraph problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736640$3ED8EEE4-2E17-48EC-A223-6840CA456D73","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"12470e61d9215272b501793c1784dc2edcecf937","datavalue":{"value":"1461.68092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$9D9BFF88-FAD1-402E-807B-89EEFBADB2C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cea5319e7e2745b67de52c92975f3077e6892afd","datavalue":{"value":{"entity-type":"item","numeric-id":507586,"id":"Q507586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$CFE1EDFF-E92C-4BA2-A5ED-BCD8822CA485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"29059e2f09a1df9f3661c0edc8342a0d775ce5bc","datavalue":{"value":{"entity-type":"item","numeric-id":329036,"id":"Q329036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$F7ACC06C-15D3-4B6D-A01A-5917F917EF34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ae9ae3d803b6f9d7df2d14c483ee95b047535f8","datavalue":{"value":{"entity-type":"item","numeric-id":175575,"id":"Q175575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$E4D96FD4-C8D3-4C60-8A7D-255AD5B0B6FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0641c4518a91d645d0a242b4e7f98721c222c827","datavalue":{"value":{"entity-type":"item","numeric-id":1736639,"id":"Q1736639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$D5B6AEFA-B838-478C-B5B0-079D84619921","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$5BDED6A9-36E7-4302-9590-28ED018F76C8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736640$63E9BD7C-CDF9-4F7B-A7AF-4B889CDCA18A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d40849aee515538f8afc4a6cb7bbb37edf668f18","datavalue":{"value":"Summary: The NP-hard \\textsc{Rainbow} \\textsc{Subgraph} problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most \\(k\\) vertices. We examine the parameterized complexity of \\textsc{Rainbow} \\textsc{Subgraph} for paths, trees, and general graphs. We show that \\textsc{Rainbow} \\textsc{Subgraph} is W[1]-hard with respect to the parameter \\(k\\) and also with respect to the dual parameter \\(\\ell :=n-k\\) where \\(n\\) is the number of vertices. Hence, we examine parameter combinations and show, for example, a polynomial-size problem kernel for the combined parameter \\(\\ell\\) and ``maximum number of colors incident with any vertex''. Additionally, we show APX-hardness even if the input graph is a properly edge-colored path in which every color occurs at most twice.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$BF766187-320D-4D4B-990A-4E21241D9DFC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$9B8B41EA-D6D6-4FF7-8F58-E83783398A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$9FBCECB2-D18D-4C9E-97AD-49AF6B68ABEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$C40F97DA-CA21-4DB7-B768-A3BE139FAF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$9888EB31-CD13-47E8-8067-EF2A7D132246","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"89a0342f3bf0d6bfb3ed86c24bf4cdc413345ed7","datavalue":{"value":"7042237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$B4ADDF7E-1F5D-4613-87BE-2BB9790735A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c562c36759035eb361c19aeaefa854e6a2248a18","datavalue":{"value":"APX-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$DE3B1BC2-627A-4956-960B-E7111600307F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"72383a36d98d6772a238d3d08d2dac58969865d6","datavalue":{"value":"multivariate complexity analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$C18D5EF2-CBD4-441C-809A-435DADC722D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1520de8379415749656b1e95045c660d5b7f1330","datavalue":{"value":"fixed-parameter tractability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$33AAA875-FAA5-46BB-9A01-2F3E7A5C3823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c8a008d8d92332f48efce6026e91ecf48c04bdf","datavalue":{"value":"parameterized hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$89FF9E11-DC41-4E80-B77B-696CAF8E8026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8472c60ee93ebdb376b5c52e2ed11c063cdbfc4f","datavalue":{"value":"problem kernel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$09C31318-BA67-4B1E-9BA9-2ECE6CD51855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97c332282ba0cd8c4206ea85da97d5ac0ada104d","datavalue":{"value":"haplotyping","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736640$1919937E-324D-4F7A-A7CE-1DDB9C414FD7","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":"Q1736640$65C1B39D-E737-423C-8C1D-C090249A1400","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8c819e8914f9e6169de4e1bd801cc7cd29a7adc7","datavalue":{"value":"https://doi.org/10.3390/a8010060","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736640$0077D2C2-B28B-4747-8168-C93D0C01A837","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"17ff9f88baa568b6289634f0d12f111be1aca731","datavalue":{"value":"W2126883946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$69F79044-FFC9-4FC1-BA0A-BADABE5EF6EE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"84f75bc295a3fc51f93e1d20c2070f0db766262b","datavalue":{"value":{"entity-type":"item","numeric-id":3545128,"id":"Q3545128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$28BB614C-5569-479C-9A89-3EB15423FA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcdf318f2426a336b0f5fbb3ffba388d5357b86e","datavalue":{"value":{"entity-type":"item","numeric-id":709311,"id":"Q709311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$5DAB4872-FECE-409D-976A-29FBCCB176E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1331bd8ae2f315ab6c8d14b767947a402236620","datavalue":{"value":{"entity-type":"item","numeric-id":1944047,"id":"Q1944047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$CAA78D51-66A4-4AFE-AD21-BF00C10D7835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2213c0feb175d6396655040b91bdd4a27e5ec751","datavalue":{"value":{"entity-type":"item","numeric-id":2250438,"id":"Q2250438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$794C9B72-2972-4851-83CA-EE365DF6CFC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e28bd5e8ac7ec6f76731337f606309289071c8f6","datavalue":{"value":{"entity-type":"item","numeric-id":2857441,"id":"Q2857441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$B3F3054E-DFDE-41F8-9257-2E282D15A386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cd0cc10879eaa23a811d1db91e295b13fba0fba","datavalue":{"value":{"entity-type":"item","numeric-id":3575249,"id":"Q3575249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$310DADA1-522C-4BED-BF4B-6F0BB32668CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8737cd899b0d18bade9c0454878d32efc7b28745","datavalue":{"value":{"entity-type":"item","numeric-id":3637124,"id":"Q3637124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$CA2D9172-2D0E-41E6-A618-581544AD81E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b58968a0c1deafa65a49fe085b615bddb97e960","datavalue":{"value":{"entity-type":"item","numeric-id":5897767,"id":"Q5897767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$693209CF-1C71-4318-98F0-848B30B9D473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9911c67630a11d4620d825fee38f35fa4cb5829d","datavalue":{"value":{"entity-type":"item","numeric-id":3010438,"id":"Q3010438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$1D756555-C24C-4E1C-8141-B8BE76C5F909","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05ccbb66f253e8aabe9f774ba9414f12634b864d","datavalue":{"value":{"entity-type":"item","numeric-id":383833,"id":"Q383833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$E24FE9D2-F40E-457E-8016-2D9DA9A3D133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae35b42269b65df7a1c59338bf97c0ea301c5c81","datavalue":{"value":{"entity-type":"item","numeric-id":2488567,"id":"Q2488567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$CE4BD6EE-9B48-4272-90F9-A11E716E7DCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1357b15aa0895d858d392a7ff419092326aafa","datavalue":{"value":{"entity-type":"item","numeric-id":5710169,"id":"Q5710169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$6941C07C-7667-4D05-97B9-2D9AFB04DA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f44a76b5719daa58c59d178eeffb178e71bb9e","datavalue":{"value":{"entity-type":"item","numeric-id":1566710,"id":"Q1566710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$DF40F321-3F00-4977-8D7D-C055F08E48F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dbb60cde7f55c02cccf62f929b356800cce32f3","datavalue":{"value":{"entity-type":"item","numeric-id":1001898,"id":"Q1001898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$EB0E66EE-F48F-4F89-BFC0-8F980C77D984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cc833c04e046c3613d9661ac4a1c39867f4a31c","datavalue":{"value":{"entity-type":"item","numeric-id":4899257,"id":"Q4899257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$C0533E7D-1F4E-4BC3-BB4A-FC1AC145A4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d078e21f9718b01f228742d1c2f5371b675a0f5","datavalue":{"value":{"entity-type":"item","numeric-id":3558013,"id":"Q3558013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$40E45557-5368-4AB8-918D-26F39D5EA49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f6f0e024114319e5eb6aae9883a0233df2f35ab","datavalue":{"value":{"entity-type":"item","numeric-id":3549598,"id":"Q3549598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$4276D505-2A12-4ABA-991E-25C562E31490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ee6e6a2ab1fbaa1f8d6432c50db632c0f09537d","datavalue":{"value":{"entity-type":"item","numeric-id":3549597,"id":"Q3549597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$C6AEF4CD-A717-4AEA-A020-2BE1BDE12ED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"876f35f4e9546c4e3a5f5566f448dbeff5f2b1be","datavalue":{"value":{"entity-type":"item","numeric-id":2925427,"id":"Q2925427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736640$AF4FAA67-81CA-49F5-895F-20E3C9C01D0D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d4c4b2bdf608aaea09a73f35135eee87171a023c","datavalue":{"value":"10.3390/A8010060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736640$A30D9E25-035A-4BEF-8872-6B8F3FFE7634","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2261fd22160eb1882af34031640ee2a24b77274","datavalue":{"value":{"entity-type":"item","numeric-id":2945198,"id":"Q2945198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3df58dfc5140ad755ee055a59ffa752c67e0db0","datavalue":{"value":{"amount":"+0.997362732887268","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":"Q1736640$B13882C4-7027-45DA-A2C0-7EF689DA97C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63a2b25e36f4c10cb572289af25667b5794870d7","datavalue":{"value":{"entity-type":"item","numeric-id":4606330,"id":"Q4606330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4e9643e290e24ca90fd44f495262dbe1a2af26a","datavalue":{"value":{"amount":"+0.8565644025802612","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":"Q1736640$61A50D79-4FF5-453A-98DA-6302085F0F86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a44e4ecfea9fcf36f58e9236353dc6a2a5138adf","datavalue":{"value":{"entity-type":"item","numeric-id":3174728,"id":"Q3174728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92c3acc0ff0ed82663d8674c5ec935bf8b14d34a","datavalue":{"value":{"amount":"+0.853543758392334","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":"Q1736640$65B3DEE0-CD14-4355-B730-9702CC1DC1F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"527ec0322f92fe59903fab43189be29983c236fd","datavalue":{"value":{"entity-type":"item","numeric-id":2925427,"id":"Q2925427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"642e713f24d81436bdf920cddde52e05b74bc938","datavalue":{"value":{"amount":"+0.8434609174728394","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":"Q1736640$505F03BF-0CAF-4CCF-8573-5FA7756720EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e41f75185631083125655c41237e9cdd9e6fac1","datavalue":{"value":{"entity-type":"item","numeric-id":2914324,"id":"Q2914324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60dcc19baea8d9233ce497f45f0299a0691baa53","datavalue":{"value":{"amount":"+0.8398656845092773","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":"Q1736640$1CD50576-055C-4F1B-9B9C-BAAC0DD1872E","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":"Q1736640$6E55B39E-916F-4C94-B781-FDB6001E9009","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736640","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736640"}}}}}