Graph Motif Problems Parameterized by Dual

Christian Komusiewicz; Guillaume Fertin

REVIEW 2 major objections 3 minor 26 references

Graph Motif Problems Parameterized by Dual

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Colorful Graph Motif cannot beat 2^ℓ on general graphs, and becomes fast on trees.

desk verdict Solid parameterized complexity paper that closes the dual-parameter question for CGM and gives tight tree algorithms; typos are minor, no load-bearing flaw. read the letter →

arxiv 1908.03870 v1 pith:G43J6DB3 submitted 2019-08-11 cs.CC cs.DSmath.CO

Guillaume Fertin , Christian Komusiewicz This is my paper · ORCID

classification cs.CCcs.DSmath.CO MSC 05C8568Q2568Q27

keywords GraphMotifColorfulList-Coloreddualparameterfixed-parametertractabilitySETHlowerboundproblemkernelparameterizedcomplexity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies three vertex-colored subgraph problems—Graph Motif, Colorful Graph Motif, and List-Colored Graph Motif—parameterized by the dual parameter ℓ = |V| − |M|, the number of vertices one must delete rather than keep. On general graphs, the central claim is that Colorful Graph Motif cannot be solved in (2−ε)^ℓ · $n^{{O(1)}}$ time unless the strong exponential time hypothesis (SETH) fails, so the known O(2^ℓ · |E|) deletion-branching algorithm is essentially optimal. It also proves that List-Colored Graph Motif remains W[1]-hard for parameter ℓ even when every vertex has a list of at most two colors. On trees the picture changes: Graph Motif becomes solvable in O(3^ℓ · n) time, Colorful Graph Motif in O(√2^ℓ + n) time with a (2ℓ+1)-vertex kernel, while Graph Motif on trees has no polynomial-size kernel unless NP ⊆ coNP/poly. The paper's point is that the dual parameter separates the easy tree case from the hard general case and yields a near-complete complexity landscape.

What carries the argument

The central objects are the dual parameter ℓ = |V| − |M| and a reduction from CNF-SAT that makes ℓ equal the number of Boolean variables. For the tree algorithms, the load-bearing machinery is a dynamic-programming table over safe rooted subtrees: a connected subtree containing the root and all vertices whose colors are non-abundant, with entries indexed by how many vertices of each abundant color are deleted. The O(3^ℓ · n) bound comes from showing that the product of per-color deletion counts is maximized when all ℓ deletions are spread one per color. For Colorful Graph Motif on trees, a two-phase kernelization contracts paths between unique vertices and then removes color-conflicting vertices, yielding the (2ℓ+1)-vertex bound.

What would settle it

Take a small CNF formula, build the Colorful Graph Motif instance described in the proof of Theorem 1, and solve it by exhaustive search: the answer must match the formula's satisfiability and the dual parameter must equal the number of variables, so any mismatch would falsify the reduction lemma on which the lower bound rests.

Watch

Extended reading notes

Core claim

For general graphs, the paper proves a SETH-based lower bound: any algorithm for Colorful Graph Motif running in (2−ε)^ℓ · $n^{{O(1)}}$ time would refute the strong exponential time hypothesis, via a polynomial reduction from CNF-SAT in which ℓ equals the number of Boolean variables. This makes the previously known O(2^ℓ · |E|) search-tree algorithm optimal up to polynomial factors. For trees, the paper proves that Graph Motif is solvable in O(3^ℓ · n) by dynamic programming over safe subtrees, that Colorful Graph Motif is solvable in O(√2^ℓ + n) by branching on repeated colors, and that Colorful Graph Motif admits a kernel with at most 2ℓ+1 vertices computed in linear time. In the other direction, it shows that Graph Motif on trees admits no polynomial-size kernel unless NP ⊆ coNP/poly, using an or-cross-composition from Multicolored Clique.

Load-bearing premise

The negative results for general graphs assume that SAT cannot be solved much faster than 2^n; if that assumption is false, the claimed optimality of the 2^ℓ algorithm for Colorful Graph Motif no longer follows.

Editorial extensions

If this is right

The O(2^ℓ · |E|) algorithm for Colorful Graph Motif on general graphs cannot be improved to (2−ε)^ℓ · n^{O(1)} unless SETH fails, so its exponential dependence on the dual parameter is essentially optimal.
Any fixed-parameter algorithm for List-Colored Graph Motif parameterized by ℓ must exploit more than list-size structure, since W[1]-hardness persists with lists of size at most two.
On trees, Graph Motif is fixed-parameter tractable for ℓ, in contrast to its W[1]-hardness on general graphs.
Colorful Graph Motif on trees is substantially easier than the general case: it has a linear-vertex kernel and a search tree of size O(√2^ℓ), giving an O(√2^ℓ + n) algorithm.
Graph Motif on trees does not admit a polynomial-size kernel for ℓ unless NP ⊆ coNP/poly, so the kernel gap between Graph Motif and Colorful Graph Motif on trees is real.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial extension: the tight SETH reduction suggests the dual parameter is the right lens for practical motif search, since the bottleneck is deleting stray occurrences of repeated colors rather than matching the motif itself.
Editorial extension: the safe-subtree dynamic programming may transfer to bounded-treewidth graphs, where the analogous table would index deletions by abundant colors across bags; the tree result is the width-one case.
Editorial extension: the open case of List-Colored Graph Motif on trees with a forest vertex-color graph might be resolved by the same branching on 2-abundant colors, with the hardness for size-two lists suggesting that the degree structure of the color-vertex graph, not list size, is what matters.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Let me cut to the point: this is a solid, standard parameterized complexity paper, and it deserves publication. The main new results are the SETH lower bound for Colorful Graph Motif parameterized by ℓ = n − |M|, showing the earlier O(2^ℓ · m) algorithm is optimal, and the W[1]-hardness of List-Colored Graph Motif with lists of size two. On trees, the paper gives an O(3^ℓ · n) algorithm for Graph Motif, proves that no polynomial kernel exists, and for Colorful Graph Motif gives a (2ℓ+1)-vertex kernel and an O(√2^ℓ + n) algorithm. These close the dual-parameter picture for CGM and considerably improve the tree case.

The reductions are clean. The CGM lower bound is the standard CNF-SAT-to-motif construction; the equivalence argument holds. The LGM hardness from Multicolored Independent Set is straightforward, and the list-size-2 restriction is a nice touch. The dynamic program for GM on trees is the right kind of DP; the recurrence correctly tracks deletion counts for abundant colors, and the O(3^ℓ) bound follows from a legitimate product maximization.

Soft spots are cosmetic rather than substantive. The recurrence for the auxiliary table D^i_v has a typo: the last coordinate should subtract occ(T_{u_i}, c_j), not occ(T_{u_i}, c_1). And in the proof of Theorem 7, the phrase "all vertices except r are unique" is wrong; the size bound follows from Lemma 2 (at most 2ℓ non-unique vertices), not from uniqueness. The cross-composition for the kernel lower bound is intricate, and I had to read the gadget construction twice to be comfortable, but the correctness argument holds together. All negative results are explicitly conditional on SETH and NP ⊄ coNP/poly, which is standard and stated up front.

I don't see a load-bearing flaw. The paper is self-contained, the citations look appropriate, and the claimed novelty checks out against the cited earlier work. This is a paper for parameterized complexity specialists, but within that audience it is a useful and complete piece of work. I would send it to a serious referee and would cite it in future work on dual parameters or motif problems.

Referee Report

2 major / 3 minor

Summary. The paper studies Graph Motif (GM), Colorful Graph Motif (CGM), and List-Colored Graph Motif (LGM) parameterized by the dual parameter ℓ = |V| − |M|. For general graphs it proves a SETH-conditional (2−ε)^ℓ · n^{O(1)} lower bound for CGM, a polynomial-kernel lower bound under NP ⊄ coNP/poly, and W[1]-hardness of LGM for ℓ even when every list has size at most two. For trees it gives an O(3^ℓ · n) dynamic program for GM, a kernelization lower bound for GM via cross-composition, an O(√2^ℓ + n) algorithm for CGM with a (2ℓ+1)-vertex kernel, and an FPT algorithm for a restricted class of LGM instances whose vertex-color graph is a forest. All results are proved by explicit reductions, dynamic-programming recurrences, or branching arguments; the paper is self-contained apart from standard hypotheses such as SETH and NP ⊄ coNP/poly.

Significance. The paper resolves or significantly tightens the parameterized complexity of three central motif problems under the dual parameter. The SETH lower bound for CGM is a clean and convincing argument that the earlier O(2^ℓ · m) algorithm is essentially optimal; the W[1]-hardness reduction for LGM with list size two is a nice strengthening; and the tree-case algorithms and kernel lower bound are natural and mostly well executed. The cross-composition lower bound for GM on trees is technically sound. The main caveat is that two of the positive tree results, the CGM kernelization and the linear-time base case of the CGM branching algorithm, are not correct as stated when the input graph contains colors absent from the motif M; the proofs appear to rely on an unstated and nontrivial assumption about such colors. If that gap is repaired, the paper would be a solid contribution.

major comments (2)

[4, Theorem 7] The equivalence proof of the kernelization is invalid when G contains colors not appearing in M. The proof claims that every occurrence of M contains all vertices removed in Phase I, because such vertices are unique or lie on paths between unique vertices; this is false for a unique vertex whose color is not in M. Concrete counterexample: let G be the path v1-v2-v3 with colors a, d, b respectively and let M = {a, b}. Then ℓ = 1 and the instance is a no-instance, since any connected set containing both colors a and b must include v2, whose color d is not in M. The kernelization, rooted at v1, finds no pendant non-unique subtrees, removes v2 and v3 in Phase I, removes b from M, and outputs the single vertex v1 with motif {a}, a yes-instance. Thus the kernelization does not preserve equivalence for general CGM instances. A component-wise reduction that first deletes vertices whose colors are absent from M appears necessary before the Phase I/Phase II argument can go through.
[4, Lemma 3] The linear-time base case is also incorrect when vertices have colors not in M. Example: let G be a star with center r of color a ∈ M and two leaves of color b ∉ M, with M = {a}. Then Branching Rule 2 does not apply, since color b occurs only in leaves. The algorithm of Lemma 3 deletes occ(b)−1 = 1 leaf of color b, leaving a graph whose colors are a and b; this graph is not an occurrence of M, although the original instance is a yes-instance because S = {r} is a valid occurrence. The proof that the remaining graph 'contains each color exactly once' does not imply that its color set equals M. The lemma needs an explicit treatment of colors absent from M, or a restriction to instances in which every color of G occurs in M, which in turn requires the component-splitting reduction mentioned above.

minor comments (3)

[3.1, DP recurrence] In the recurrence for D^i_v, the first case writes the last coordinate as λ_j − occ(T_ui, c1); the second occurrence of c1 should be c_j, so that the expression reads λ_j − occ(T_ui, c_j).
[4, Theorem 7 proof] The sentence 'the resulting instance has at most 2ℓ+1 vertices since all vertices except r are unique' states the condition backwards: after the kernelization, r is the only unique vertex and all other vertices are non-unique, so Lemma 2 bounds their number by 2ℓ. As printed, the sentence contradicts the use of Lemma 2.
[3.2, Reduction Rule 3] The proof of Rule 3 says that each costly component forces at least one deleted vertex; this is correct, but the phrase 'all color vertices c in H′ have multiplicity exactly deg_H(c)−1' should be read as multiplicity in M, which is clear from context but could be stated explicitly.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper is self-contained; lower bounds are direct SETH/parameterized reductions and upper bounds are explicit algorithms and kernels.

full rationale

The paper's derivation chain is self-contained. Theorem 1 is a standard polynomial-time reduction from CNF-SAT to Colorful Graph Motif in which the dual parameter is set equal to the number of variables, so the SETH lower bound follows directly from the reduction and the SETH assumption; the O(2^ell * m) algorithm of Betzler et al. [2] that it matches is external prior work and is not an input to the reduction. The W[1]-hardness proofs for List-Colored Graph Motif (Theorem 3, Corollary 1) and the cross-composition for Graph Motif on trees (Theorem 6) reduce Multicolored Independent Set and Multicolored Clique, respectively, with the parameter identities ell=k or ell=|D| verified in the proof, and no fitted parameters are renamed as predictions. The positive tree results are proved by explicit dynamic-programming recurrences (Theorem 4), concrete branching rules with a stated branching factor (Theorem 8), and a kernelization whose correctness is argued by a claim about which vertices every occurrence must contain and avoid (Theorem 7). The few self-citations in the paper, notably to [2], [12], and [14], are either contextual or used as previously published external results, and they are not load-bearing premises that force the present conclusions. Minor typographical slips, such as the repeated c1 in the displayed D_i^v recurrence and the use of 'unique' where the context means 'non-unique' in the kernelization discussion, do not change the fact that no claim is defined in terms of its own conclusion.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claims rest on standard complexity hypotheses (SETH, NP ⊄ coNP/poly, W[1] ≠ FPT) which are stated explicitly in the paper. No parameters are fitted to data and no new physical or mathematical entities are postulated.

assumptions (3)

domain assumption The Strong Exponential Time Hypothesis (SETH): CNF-SAT cannot be solved in (2−ε)^n · poly(m) time for any ε > 0.
Used in Theorem 1 to rule out (2−ε)^ℓ algorithms for CGM on general graphs. If SETH is false, the lower bound does not imply optimality.
domain assumption NP is not contained in coNP/poly.
Used in Theorems 2 and 6 to exclude polynomial-size problem kernels. The results are conditional on this standard complexity assumption.
domain assumption W[1] is not equal to FPT.
W[1]-hardness results (Theorem 3, Corollary 1) are reductions; their interpretation as fixed-parameter intractability assumes W[1] ≠ FPT.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Graph Motif Problems Parameterized by Dual." pith.science (2026). https://pith.science/paper/G43J6DB3

@misc{pith2026190803870,
  author       = {Pith},
  title        = {Pith review of: Graph Motif Problems Parameterized by Dual},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G43J6DB3}},
  note         = {Machine review of arXiv:1908.03870}
}

abstract

Let $G=(V,E)$ be a vertex-colored graph, where $C$ is the set of colors used to color $V$. The Graph Motif (or GM) problem takes as input $G$, a multiset $M$ of colors built from $C$, and asks whether there is a subset $S\subseteq V$ such that (i) $G[S]$ is connected and (ii) the multiset of colors obtained from $S$ equals $M$. The Colorful Graph Motif (or CGM) problem is the special case of GM in which $M$ is a set, and the List-Colored Graph Motif (or LGM) problem is the extension of GM in which each vertex $v$ of $V$ may choose its color from a list $\mathcal{L}(v)\subseteq C$ of colors. We study the three problems GM, CGM, and LGM, parameterized by the dual parameter $\ell:=|V|-|M|$. For general graphs, we show that, assuming the strong exponential time hypothesis, CGM has no $(2-\epsilon)^\ell\cdot |V|^{\mathcal{O}(1)}$-time algorithm, which implies that a previous algorithm, running in $\mathcal{O}(2^\ell\cdot |E|)$ time is optimal [Betzler et al., IEEE/ACM TCBB 2011]. We also prove that LGM is W[1]-hard with respect to $\ell$ even if we restrict ourselves to lists of at most two colors. If we constrain the input graph to be a tree, then we show that GM can be solved in $\mathcal{O}(3^\ell\cdot |V|)$ time but admits no polynomial-size problem kernel, while CGM can be solved in $\mathcal{O}(\sqrt{2}^{\ell} + |V|)$ time and admits a polynomial-size problem kernel.

Figures

Figures reproduced from arXiv: 1908.03870 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

Ambalath, Radheshyam Balasundaram, Chint an Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, and M

Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chint an Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, and M. S. Ramanujan. O n the kernelization complexity of colorful motifs. In Proceedings of the 5th International Symposium on Paramete rized and Exact Computation (IPEC ’10) , volume 6478 of Lecture Notes in Computer Science , pages 14–2...

work page 2010
[2]

Fellows, and Rolf Nie- dermeier

Nadja Betzler, René van Bevern, Christian Komusiewicz, Michael R. Fellows, and Rolf Nie- dermeier. Parameterized algorithmics for ﬁnding connecte d motifs in biological networks. IEEE/ACM Transactions on Computational Biology and Bioinf ormatics, 8(5):1296–1308, 2011

work page 2011
[3]

C onstrained multilinear detection and generalized graph motifs

Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. C onstrained multilinear detection and generalized graph motifs. Algorithmica, 74(2):947–967, 2016. 18

work page 2016
[4]

Bodlaender, Bart M

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch . Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics , 28(1):277–305, 2014

work page 2014
[5]

Bodlaender, Stéphan Thomassé, and Anders Yeo

Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Ke rnel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science , 412(35):4570–4578, 2011

work page 2011
[6]

The Graph Motif probl em parameterized by the structure of the input graph

Édouard Bonnet and Florian Sikora. The Graph Motif probl em parameterized by the structure of the input graph. Discrete Applied Mathematics , 231:78–94, 2017

work page 2017
[7]

Karp, Ron Shami r, and Roded Sharan

Sharon Bruckner, Falk Hüﬀner, Richard M. Karp, Ron Shami r, and Roded Sharan. Topology- free querying of protein interaction networks. Journal of Computational Biology , 17(3):237–252, 2010

work page 2010
[8]

Fomin, Lukasz Kowalik, Daniel Loks htanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Loks htanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015

work page 2015

Show all 26 references

[9]

Vinod Reddy

Bireswar Das, Murali Krishna Enduri, Neeldhara Misra, a nd I. Vinod Reddy. On structural parameterizations of Graph Motif and Chromatic Number. In Proceedings of the Third Inter- national Conference on Algorithms and Discrete Applied Mat hematics (CALDAM ’17) , volume 10156 of...

2017
[10]

Satisﬁability al lows no nontrivial sparsiﬁcation unless the polynomial-time hierarchy collapses

Holger Dell and Dieter van Melkebeek. Satisﬁability al lows no nontrivial sparsiﬁcation unless the polynomial-time hierarchy collapses. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC ’10) , pages 251–260. ACM, 2010

2010
[11]

Downey and Michael R

Rod G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013

2013
[12]

Fellows, Guillaume Fertin, Danny Hermelin, and Stéphane Vialette

Michael R. Fellows, Guillaume Fertin, Danny Hermelin, and Stéphane Vialette. Upper and lower bounds for ﬁnding connected motifs in vertex-colored graphs. Journal of Computer and System Sciences, 77(4):799–811, 2011

2011
[13]

Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette

Michael R. Fellows, Danny Hermelin, Frances Rosamond, and Stéphane Vialette. On the parameterized complexity of multiple-interval graph prob lems. Theoretical Computer Science , 410(1):53–61, 2009

2009
[14]

A lgorithmic aspects of the Maximum Colorful Arborescence problem

Guillaume Fertin, Julien Fradin, and Géraldine Jean. A lgorithmic aspects of the Maximum Colorful Arborescence problem. In Proceedings of the 14th Annual Conference on Theory and Applications of Models of Computation (TAMC ’17) , volume 10185 of Lecture Notes in Computer Scien...

2017
[15]

On the Maximum Colorful Ar- borescence problem and color hierarchy graph structure

Guillaume Fertin, Julien Fradin, and Christian Komusi ewicz. On the Maximum Colorful Ar- borescence problem and color hierarchy graph structure. In Gonzalo Navarro, David Sankoﬀ, and Binhai Zhu, editors, Proceedings of the 29th Annual Symposium on Combinatorial P attern Matchi...

2018
[16]

Fomin and Dieter Kratsch

Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms . Springer-Verlag, 1st edition, 2010. 19

2010
[17]

Twin-cover: Beyond vertex cover in para meterized algorithmics

Robert Ganian. Twin-cover: Beyond vertex cover in para meterized algorithmics. In Proceedings of the 6th International Symposium on Parameterized and Exa ct Computation (IPEC ’11) , volume 7112 of Lecture Notes in Computer Science , pages 259–271. Springer, 2011

2011
[18]

Parameterized algorithmics and computational experiments for ﬁnding 2-clubs

Sepp Hartung, Christian Komusiewicz, and André Nichte rlein. Parameterized algorithmics and computational experiments for ﬁnding 2-clubs. Journal of Graph Algorithms and Applications , 19(1):155–190, 2015

2015
[19]

Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512–530, 2001

Russell Impagliazzo, Ramamohan Paturi, and Francis Za ne. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512–530, 2001

2001
[20]

Fernandes, and Marie-Fra nce Sagot

Vincent Lacroix, Cristina G. Fernandes, and Marie-Fra nce Sagot. Motif search in graphs: Application to metabolic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(4):360–368, 2006

2006
[21]

A general metho d to speed up ﬁxed-parameter- tractable algorithms

Rolf Niedermeier and Peter Rossmanith. A general metho d to speed up ﬁxed-parameter- tractable algorithms. Information Processing Letters , 73(3-4):125–129, 2000

2000
[22]

Pinter, Hadas Shachnai, and Meirav Zehavi

Ron Y. Pinter, Hadas Shachnai, and Meirav Zehavi. Deter ministic parameterized algorithms for the Graph Motif problem. Discrete Applied Mathematics , 213:162–178, 2016

2016
[23]

Pinter and Meirav Zehavi

Ron Y. Pinter and Meirav Zehavi. Algorithms for topolog y-free and alignment network queries. Journal of Discrete Algorithms , 27:29–53, 2014

2014
[24]

Finding maximum col- orful subtrees in practice

Imran Rauf, Florian Rasche, François Nicolas, and Seba stian Böcker. Finding maximum col- orful subtrees in practice. Journal of Computational Biology , 20(4):311–321, 2013

2013
[25]

Modeling cellular machin ery through biological network com- parison

Roded Sharan and Trey Ideker. Modeling cellular machin ery through biological network com- parison. Nature biotechnology, 24(4):427–433, 2006

2006
[26]

An (almost complete) state of the art ar ound the Graph Motif problem

Florian Sikora. An (almost complete) state of the art ar ound the Graph Motif problem. Tech- nical report, LIGM Université Paris-Est, March 2012. 20

2012

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Ambalath, Radheshyam Balasundaram, Chint an Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, and M

Abhimanyu M. Ambalath, Radheshyam Balasundaram, Chint an Rao H., Venkata Koppula, Neeldhara Misra, Geevarghese Philip, and M. S. Ramanujan. O n the kernelization complexity of colorful motifs. In Proceedings of the 5th International Symposium on Paramete rized and Exact Computation (IPEC ’10) , volume 6478 of Lecture Notes in Computer Science , pages 14–2...

work page 2010

[2] [2]

Fellows, and Rolf Nie- dermeier

Nadja Betzler, René van Bevern, Christian Komusiewicz, Michael R. Fellows, and Rolf Nie- dermeier. Parameterized algorithmics for ﬁnding connecte d motifs in biological networks. IEEE/ACM Transactions on Computational Biology and Bioinf ormatics, 8(5):1296–1308, 2011

work page 2011

[3] [3]

C onstrained multilinear detection and generalized graph motifs

Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. C onstrained multilinear detection and generalized graph motifs. Algorithmica, 74(2):947–967, 2016. 18

work page 2016

[4] [4]

Bodlaender, Bart M

Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch . Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics , 28(1):277–305, 2014

work page 2014

[5] [5]

Bodlaender, Stéphan Thomassé, and Anders Yeo

Hans L. Bodlaender, Stéphan Thomassé, and Anders Yeo. Ke rnel bounds for disjoint cycles and disjoint paths. Theoretical Computer Science , 412(35):4570–4578, 2011

work page 2011

[6] [6]

The Graph Motif probl em parameterized by the structure of the input graph

Édouard Bonnet and Florian Sikora. The Graph Motif probl em parameterized by the structure of the input graph. Discrete Applied Mathematics , 231:78–94, 2017

work page 2017

[7] [7]

Karp, Ron Shami r, and Roded Sharan

Sharon Bruckner, Falk Hüﬀner, Richard M. Karp, Ron Shami r, and Roded Sharan. Topology- free querying of protein interaction networks. Journal of Computational Biology , 17(3):237–252, 2010

work page 2010

[8] [8]

Fomin, Lukasz Kowalik, Daniel Loks htanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh

Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Loks htanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015

work page 2015