11

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach. This has been observed, for instance, in Theorem 17 in Pierluigi Crescenzi and LucaTrevisan: "Max NP-completeness made easy" Theoretical Computer Science 28, (1999), Pages 65-79


7

I recommend reading Sections 7 and 14 in the excellent book by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh. In short, Gu and Tamaki give a quadratic time algorithm which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then Robertson and Seymour in (5.1) give a tree-decomposition of width less than ...


5

The obvious resource for planar graphs in Coq would be the (modern port of) the four color theorem in Coq/SSReflect, by Georges Gonthier (and others) which obviously does need to define planar graphs. It's not immediately obvious to me how planar graphs are characterized, though the relevant file is here and it seems to involve a combination of Euler ...


5

It can be solved in linear time in an even more general class of graphs: As shown in N. Bourgeois, A. Giannakos, G. Lucarelli, I. Milis, V.T. Paschos Exact and approximation algorithms for densest $k$-subgraph WALCOM’13, LNCS, vol. 7748, Springer-Verlag (2013), pp. 114-125 the Densest-$k$-Subgraph problem can be solved in $O(2^{\mathrm{tw}(G)}\cdot k \cdot ...


4

I just wanted to make some additional comments not already covered by Cody's nice answer, and also address question (2). First, Gonthier goes into detail about the representation of planar maps used for the formalization of 4CT in his technical report A computer-checked proof of the Four Colour Theorem. This representation is based on the classical (and ...


2

Let $A, B$ be the bipartition of $G$ and $|A| = |B| = n.$ Claim: $c_1 + c_2 + c_3 \equiv n \pmod{2}.$ To show this, we can naturally associate each matching $M_i$ to a permutation $\sigma_i \in S_n.$ Define $f: S_n \to \{0, 1\}$ such that $f(\sigma) = 0$ iff $\sigma$ is an even permutation, and define $c: S_n \to \mathbb{N}$ so that $c(\sigma)$ is the ...


2

For graphs embedded on a surface of genus g with bounded weights $w:E \rightarrow \mathbb{Z}$, you can solve MAX-CUT in time $4^g poly(n)$ using an algorithm of Gallucio, Loebl and Vondrák. Applying it to your instance after taking the opposite weights and looking whether the result is positive seems to solve your problem.


2

Yes, it is still $NP$ complete. This is because of: Claim: All Hamiltonian cycles on maximal planar graphs are balanced. Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/wiki/Grinberg%27s_theorem


Only top voted, non community-wiki answers of a minimum length are eligible