ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Algorithms, Vol. 8, Pages 60-81: The Parameterized Complexity of the Rainbow Subgraph Problem (2015)

Falk Hüffner; Christian Komusiewicz; Rolf Niedermeier; Martin Rötzschke

MDPI Publishing

In: Algorithms

add to mindlist on the mindlist

Details

Publication Date: 2015-02-28

Description: The NP-hard RAINBOW 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 RAINBOW SUBGRAPH for paths, trees, and general graphs. We show that RAINBOW 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.

Electronic ISSN: 1999-4893

Topics: Computer Science

Published by MDPI Publishing

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit