ECCC-Report TR09-009https://eccc.weizmann.ac.il/report/2009/009Comments and Revisions published for TR09-009en-usTue, 26 Jan 2010 02:53:22 +0200
Revision 2
| Checking Equality of Matroid Linear Representations and the Cycle Matching Problem. |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2009/009#revision2Given linear representations M1 and M2 of matroids over a field F, we consider the problem (denoted by ECLR[F]) of checking if M1and M2 represent the same matroid over F. When F =Z _2, we show that ECLR[Z _2] is complete for $\oplus$L under logspace many-one reductions.
When F=Q, given linear representations M1,M2$\in$Q$^{m\times n}$ as input, any $X\subseteq \{1,\ldots ,n\}$ such that columns corresponding to indexes in $X$ form a minimal linearly dependent set of vectors in one linear representation but the column vectors corresponding to indexes in $X$ are linearly independent in the other linear representation is a witness that M1 and M2 represent different matroids over Q. We show that the decision and the search version of this problem are polynomial time equivalent.
We define the CYCLE MATCHING problem of checking if for a pair of undirected graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ given as input with $V_1=V_2=\{ 1,\ldots ,n\}$ and $n=|V_1|=|V_2|$, whether the set of vertices in $X\subseteq V_1$ form a cycle in $G_1$ if and only if the vertices in $X\subseteq V_2$ form a cycle in $G_2$ also, for all $X\subseteq \{ 1,\ldots ,n\}$. We show that CYCLE MATCHING is complete for L.
Also the problem of counting the number of $X\subseteq \{ 1,\ldots ,n\}$ such that vertices with indexes in $X$ form a cycle in one of the input graphs but not in the other is shown to be #P-complete.
Tue, 26 Jan 2010 02:53:22 +0200https://eccc.weizmann.ac.il/report/2009/009#revision2
Revision 1
| Checking Equality of Matroid Linear Representations and the Cycle Matching Problem |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2009/009#revision1Given linear representations $M_1$ and $M_2$ of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid over F. We show that when F=$Z_2$, ECLR{Z_2} is complete for $\parityL$. When F=$Q$, given linear representations $M_1,M_2\in \Q ^{m\times n}$ as input, any set of indexes $X \subseteq \{1,\ldots ,n\}$ such that columns corresponding to these indexes in $X$ are linearly dependent in one linear representation but are linearly independent in the other linear representation is a witness that $M_1$ and $M_2$ represent different matroids over $Q$. We show that the decision and the search version of this problem are polynomial time equivalent.
We consider the CYCLEMATCHING problem of checking if for a pair of undirected graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ given as input with $n=|V_1|=|V_2|$, we check if the set of vertices having indexes in $X\subseteq {1,...,n}$ form a cycle in $G_1$ if and only if the corresponding set of vertices having indexes in $X\subseteq {1,...,n}$ form a cycle in $G_2$ for all $X\subseteq {1,...,n}$. We show that CYCLEMATCHING is complete for L. Also the problem of counting the number of $X\subseteq {1,...,n}$ such that vertices with indexes in X form a cycle in one of the input graphs but not in the other is shown to be #P-complete.
Thu, 06 Aug 2009 07:41:12 +0300https://eccc.weizmann.ac.il/report/2009/009#revision1
Paper TR09-009
| Checking Equality of Matroid Linear Representations and the Cycle Matching Problem |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2009/009Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given as input. Then any set of indexes, columns corresponding to which are linearly dependent in one representation but are linearly independent in another is a witness that M_1 and M_2 represent different matroids over Q. We show that the decision and the search version of this problem are polynomial time equivalent. We consider the CYCLEMATCHING problem of checking if for a pair of undirected graphs G_1=(V_1,E_1) and G_2=(V_2,E_2) given as input with |V_1|=|V_2|=n, whether any set of vertices having indexes in X\subseteq {1,...,n} form a cycle in G_1 if and only if the corresponding set of vertices form a cycle in G_2. We show that CYCLEMATCHING is complete for L. Also the problem of counting the number of X\subseteq {1,...,n}$ such that vertices with indexes in X form a cycle in one of the input graphs but not in the other is shown to be $\sharpP$-complete.
Thu, 05 Feb 2009 19:56:33 +0200https://eccc.weizmann.ac.il/report/2009/009