Abstract
The Graph Motif problem asks whether a given multiset of colors appears on a connected subgraph of a vertex-colored graph. The fastest known parameterized algorithm for this problem is based on a reduction to the k-Multilinear Detection (k-MlD) problem: the detection of multilinear terms of total degree k in polynomials presented as circuits. We revisit k-MlD and define k-CMlD, a constrained version of it which reflects Graph Motif more faithfully. We then give a fast algorithm for k-CMlD. As a result we obtain faster parameterized algorithms for Graph Motif and variants of it.
Original language | English (US) |
---|---|
Pages (from-to) | 889-892 |
Number of pages | 4 |
Journal | Information Processing Letters |
Volume | 112 |
Issue number | 22 |
DOIs | |
State | Published - Nov 30 2012 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications
Keywords
- Graph algorithms
- Parameterized algorithms
- Randomized algorithms