All Questions

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...

We got a reduction maximum independent set to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses. Let $G$ be graph of order $n$ and ...

I'm currently developing an algorithm for computing knot coloring invariants and got to the following question: Given a set $S$ and a certain hyper-graph $H \subseteq S^3 $, find a decomposition $S = ...

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...

According to a conjecture: Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common. Equivalent statement here Main question: ...

Found a possible reduction from recognizing lexicographic product of graphs to 2SAT (since 2SAT is polynomial, the algorithm is polynomial). Can't prove completeness of the algorithm and since it is ...