CSP (Constraint Satisfaction Problem) degree degree =2 max-degree≤d ≤d 8 matching constraint matchings: variables xi∈{0,1} (at-most-1) matching constraint independent sets: variables i∈{0，l} (at-most-1) partition function: Z= 入川1 i∈{0，l}n satisfying all constraints
CSP (Constraint Satisfaction Problem) 1 2 3 4 5 6 a b c d e f g 1 2 3 4 5 6 a b c d e f g matchings: independent sets: variables xi 2 {0, 1} matching constraint (at-most-1) matching constraint (at-most-1) variables xi 2 {0, 1} max-degree ≤ d partition function: Z = X ~x2{0,1}n satisfying all constraints k~xk1 degree ≤ d degree = 2
CSP (Constraint Satisfaction Problem) deg≤d+l deg≤k+l c2 t> c☒ 4 c函 a Boolean at-most-1 variables constraints partition function: ∑ 入川1 i∈{0,1}n satisfying all constraints
CSP (Constraint Satisfaction Problem) Boolean variables deg ≤ d+1 deg ≤ k+1 x1 x2 x3 x4 x5 c1 c2 c3 c4 c5 c6 c7 Z = X ~x2{0,1}n satisfying all constraints k~ xk1 partition function: at-most-1 constraints
Hypergraph matching hypergraph =(V,E) vertex set V hyperedge e∈E,eCV a matching is an subset MCE of disjoint hyperedges partition .U] Zλ(H)= ∑ λM川 .U4 i. functions: M:matching of H ,5 .29 8 es .6 e2 es Gibbs λXM distribution: u(M)= Z(孔)
v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 v1 v2 v3 v4 v5 v6 v7 v8 v9 e1 e2 e3 e4 e5 Hypergraph matching Z(H) = X M: matching of H |M| hypergraph H = (V,E) vertex set V hyperedge e 2 E, e ⇢ V a matching is an subset M⊂E of disjoint hyperedges µ(M) = |M| Z(H) partition functions: Gibbs distribution:
matchings in hypergraphs of max-degree sk+1 and max-edge-sizes d+1 matching 01 .4 th2. incidence graph primal: .5 ,28 e3 6 9 e2 e3 5 6 dual: CSP defined by matching(packing)constraint 7 06 independent set independent sets in hypergraphs of max-degree sd+1 and max-edge-size sk+1 independent sets:a subset of non-adjacent vertices (to be distinguished with:vertex subsets containing no hyperedge as subset)
v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 v1 v2 v3 v4 v5 v6 v7 v8 v9 e1 e2 e3 e4 e5 matchings in hypergraphs of max-degree ≤ k+1 and max-edge-size ≤ d+1 v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 * * * * * * * * * * * * * * v5 * v6 * e2 * v1 * v2 * e1 * v3 * v4 * e5 * e3 * e4 * v7 * v8 * v9 * incidence graph primal: dual: v3 e1 v1 v2 v4 v8 v7 e2 e3 e5 v9 v6 v5 e4 * * * * * * * * * * * * * * v5 * v6 * e2 * v1 * v2 * e1 * v3 * v4 * e5 * e3 * e4 * v7 * v8 * v9 * matching independent set CSP defined by matching(packing) constraint independent sets in hypergraphs of max-degree ≤ d+1 and max-edge-size ≤ k+1 independent sets: a subset of non-adjacent vertices (to be distinguished with: vertex subsets containing no hyperedge as subset)
Known results deg≤d+l ☑deg≤k+l C2 independent sets of hypergraphs of max-degree≤d+1 and max-edge-size≤k+l C4 cs partition function: Z= 入川1 元∈{0,1}n satisfying Boolean at-most-1 all constraints variables constraints Classification of approximability in terms of )d,k? ●k=l:hardcore model d=1:monomer-dimer model ●forλ=1： [Dudek,Karpinski,Rucinski,Szymanska 2014]:FPTAS when d=2,k<2 [Liu and Lu 2015]FPTAS when d=2,k<3
Known results • k=1: hardcore model • d=1: monomer-dimer model •for λ=1: •[Dudek, Karpinski, Rucinski, Szymanska 2014]: FPTAS when d=2, k≤2 •[Liu and Lu 2015] FPTAS when d=2, k≤3 Boolean variables deg ≤ d+1 deg ≤ k+1 x1 x2 x3 x4 x5 c1 c2 c3 c4 c5 c6 c7 at-most-1 constraints Z = X ~x2{0,1}n satisfying all constraints k~ xk1 partition function: independent sets of hypergraphs of max-degree ≤ d+1 and max-edge-size ≤ k+1 Classification of approximability in terms of λ, d, k ?