CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Fixed-parameter tractability of error correction in graphical linear systems

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers)) ; Ömer Egecioglu ; Leonid Molokov (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
7th International Workshop on Algorithms and Computation WALCOM 2013, Lecture Notes in Computer Science Vol. 7748 (2013), p. 245-256.
[Konferensbidrag, refereegranskat]

In an overdetermined and feasible system of linear equations Ax=b, let vector b be corrupted, in the way that at most k entries are off their true values. Assume that we can check in the restricted system given by any minimal dependent set of rows, the correctness of all corresponding values in b. Furthermore, A has only coefficients 0 and 1, with at most two 1s in each row. We wish to recover the correct values in b and x as much as possible. The problem arises in a certain chemical mixture inference application in molecular biology, where every observable reaction product stems from at most two candidate substances. After formalization we prove that the problem is NP-hard but fixed-parameter tractable in k. The FPT result relies on the small girth of certain graphs.

Nyckelord: sparse system of linear equations, error correction, girth, even cycle matroid, parameterized algorithm



Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-02-15. Senast ändrad 2015-02-11.
CPL Pubid: 173657