Some Hard Problems on Matroid Spikes
| Authors | |
|---|---|
| Year of publication | 2007 |
| Type | Article in Periodical |
| Magazine / Source | Theory of Computing Systems |
| MU Faculty or unit | |
| 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: |