0
$\begingroup$

Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a collection of linear equations over $\mathbb{F}_{p}$ is satisfiable to deciding whether there is a perfect matching in a graph.

I'm aware that there are polynomial time algorithms for the perfect matching problem, and so I'm happy to allow even exponential-time reductions.

Edit: a clarification on the exponential-time reduction. I suppose what I'm really interested in is a sort of "embedding" of linear equations into perfect matchings. I.e., given some collection $\mathcal{C}$ of linear equations over $\mathbb{F}_{p}$ with variables $x_{i}$, construct (in any amount of time) a graph $G_{\mathcal{C}}$ such that if $G_{\mathcal{C}}$ has a perfect matching then we can construct assignments to $x_{i}$ to satisfy $\mathcal{C}$ efficiently (say, each $x_{i}$ can be log-space constructed from the perfect matching).

E.g., It is okay to reduce $\mathcal{C}$ to an exponential-sized graph $G_{\mathcal{C}}$ as long as I can express $x_{i}$ as some nice algebraic function, for example, of matched vertices.

Improve this question
$\endgroup$
4
  • $\begingroup$ You might want to reformulate your question. If you allow exponential time (and since you're working in a finite field) you can get a reduction by brute-forcing the solution to the equations. If there is a solution, return a graph with two vertices and one edge between them (which is a yes instance for perfect matching). If the answer is no return a graph with one vertex and no edges (which is a no instance). $\endgroup$
    – Steven
    Nov 1 at 0:24
  • $\begingroup$ That's right. I mean, determining whether a collection of linear equations is satisfiable is even solvable in polynomial time via Gaussian elimination. I suppose what I'm looking for is not only a transformation of the problem but a corresponding transformation of solutions. I.e., given a choice of matchings, I want to be able to construct assignments of the variables of the linear equation. $\endgroup$
    – dsjoint
    Nov 1 at 1:20
  • $\begingroup$ After your edit, Steven's comment still applies. You can construct assignments to $x_i$ to satisfy $\mathcal{C}$ efficiently (simply by ignoring the graph and using Gaussian elimination). I don't think the problem is well-formulated yet. Also, please don't use "Edit:". Just revise the problem so it reads well for someone who encounters it for the first time. $\endgroup$
    – D.W. ♦
    Nov 1 at 21:07
  • $\begingroup$ @D.W. I'm not sure if you can implement Gaussian elimination to obtain assignments in log-space, can you? $\endgroup$
    – dsjoint
    Nov 2 at 4:16

1 Answer 1

Reset to default
0
$\begingroup$

This is trivially possible.

  1. Solve the system $\mathcal{C}$ of linear equations, using Gaussian elimination.

  2. If there is no solution to the system of linear equations, output a graph $\mathcal{G_C}$ with one vertex and no edges (which has no perfect matching).

  3. If there is a solution to the system of linear equations, say with values $v_1,\dots,v_n$ for the variables $x_1,\dots,x_n$, then output a graph $\mathcal{G_C}$ that has a perfect matching and that encodes the values $v_1,\dots,v_n$. There are many ways to encode these values into the set of perfect graphs. For instance, add one component for each $v_i$; $v_i$ is encoded as a cycle of $2i$ vertices attached to a path of length $2v_i$. Then the graph $\mathsf{G_C}$ is a collection of these (disjoint) components, one for each $i$.

Now, given a graph $\mathcal{G_C}$ with a perfect matching, you can decode to recover the values $v_1,\dots,v_n$. For instance, with the encoding listed above, it is easy to decode in log-space.

To make the problem meaningful, you need to restrict both the generation of $\mathcal{G_C}$ and the reconstruction of the solution to both be in some complexity class (e.g., logspace) that is so limited that you can't solve linear equations within that complexity class. If you allow the generation of $\mathcal{G_C}$ to take exponential time (or polynomial time), it trivializes the problem.

Improve this answer
$\endgroup$
1
  • $\begingroup$ OK, sure. Let's say that the generation and reconstruction have to both be in logspace, then, as that is even stronger than what I want. Intuitively, what I want to just capture is the "obliviousness" of reduction to whether $\mathcal{C}$ is satisfiable or not. The only reason why I'm allowing for exponential time is because it's fine for $\mathcal{G}_{\mathcal{C}}$ to be much larger than $\mathcal{C}$ as long as I can still extract the solution efficiently. E.g., a reduction from 3COL to 3SAT where the 3SAT instance has exponentially many always satisfied dummy variables is fine. $\endgroup$
    – dsjoint
    Nov 2 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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