1
$\begingroup$

I am interested in the following quantity. Suppose we are given a matrix $M\in \mathbb{F}_2^{m\times n}$ and a string $z\in \{0,1\}^n$. I am interested in finding the largest subset $S$ of rows in M such that the following holds: for every $i\in [n]$, there is $at$ $most$ one row in $v\in S$ such that $v_i\neq z_i$.

I was wondering if this combinatorial notion has been used to characterize some complexity in literature? Any reference/ pointer is welcome. I am not interested in an algorithm to find the largest subset, but rather if such a combinatorial notion has been used to character some "other complexity measure"

$\endgroup$
  • $\begingroup$ What do you want to know about it? Are you looking for an algorithm to solve this problem? Are you trying to prove bounds on the size of the largest subset? Something else? Can you edit your post to ask a more specific question? What's the context where you ran across this? Is it an exercise? Is there some application? $\endgroup$ – D.W. Aug 17 '16 at 22:36
1
$\begingroup$

Your problem can be solved in polynomial time, by reduction to bipartite matching. In other words, there is a polynomial-time algorithm to find the largest subset $S$ of rows with your desired property.

Construct an undirected bipartite graph with $m$ left-vertices (one per row) and $n$ right-vertices (one per columN). Add an edge $(i,j)$ whenever $M_{i,j} \ne z_j$. Now each subset of rows with your property corresponds to a matching in this bipartite graph: take $S$ to be the set of left-vertices covered by the matching. In particular, the maximum matching in this graph corresponds to the largest subset of rows that satisfies your property. You can compute the maximum matching in polynomial time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.