Polynomial-time minor containment conjecture for fixed codes

Fix a code M{\mathcal M}. Given a code C{\mathcal C} of length nn, polynomial-time minor-containment conjecture. It is decidable in time polynomial in nn whether C{\mathcal C} contains M{\mathcal M} as a minor.

This is an algorithmic counterpart to finite excluded-minor characterizations: testing containment of a fixed minor would provide an efficient recognition procedure for the corresponding excluded-minor class. The source gives no resolution status.

Sources & referencesView supporting material

Primary source

Navin Kashyap, “A Decomposition Theory for Binary Linear Codes”, arXiv:cs/0611028 (2007).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.