Some Hard Problems on Matroid Spikes

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr

Year of publication 2007
Type Article in Periodical
Magazine / Source Theory of Computing Systems
MU Faculty or unit

Faculty of Informatics

Citation
Web doi
Field Informatics
Keywords matroid; spike; representability; minor
Description Spikes form an interesting class of $3$-connected matroids of branch-width~$3$. We show that some computational problems are hard on spikes with given matrix representations over infinite fields. Namely, the question whether a given spike is the free spike is co-$NP$-hard (though the property itself is definable in monadic second-order logic); and the task to compute the Tutte polynomial of a spike is $\#P$-hard (even though that can be solved efficiently on all matroids of bounded branch-width which are represented over a finite field).
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.