Largest subspace that doesn't intersect a given set

Question

Let V be a vector space over Z/2, and let X be a subset of V. Is there an algorithm to find the largest possible subspace of V which doesn't intersect X? Is it NP complete?

Answer 1

The problem is NP hard. Here's a reduction to it from 4-colorability. Given a graph with vertex set $G$ [not $V$ because that's supposed to be a vector space] and edge set $E$, form a vector space $V$ over $\mathbb{Z}/2$ having $G$ as a basis. Identify each edge $e$ with the vector that is the difference of the two endpoints of $e$, and let $S$ be the set of these edges-qua-vectors. [I know that "difference" is the same as "sum" here, but it helps to think of the edges as differences.] Then each of the following statements is easily equivalent to the next, for any fixed natural number $t$. [In the end, I'll only need the case $t=2$.]

(1) $V$ has a subspace of codimension at most $t$ that misses $S$.

(2) There are $t$ linear functionals $f:V\to\mathbb{Z}/2$ such that each edge $e$ is sent to 1 by at least one of these functionals.

(3) There are $t$ linear functionals $f:V\to\mathbb{Z}/2$ such that, for each edge $e$, at least one of these functionals takes different values at the two endpoints of $e$.

(4) There are $t$ functions $g:G\to\mathbb{Z}/2$ such that, for each edge $e$, at least one of these functions takes different values at the two endpoints of $e$.

(5) There is a function $h$ from $G$ to $(\mathbb{Z}/2)^t$ taking different values at the two ends of each edge.

(6) The graph $(G,E)$ is $2^t$-colorable.

In particular, $V$ has a codimension-2 subspace missing $S$ if and only if $G$ is 4-colorable. Since 4-colorability is known to be an NP-complete problem, the vector subspace problem is also NP-hard.

I believe the "correct" generality for this idea is what's called the critical problem for matroids. What I've presented is the special case of graphic matroids.