It's well known that planar graphs from a closed-family with forbidden minors $K_{3,3}, K_{5}$, graphs with bounded treewidth also are closed family graphs with no $H_{k}$ as minor.

I assume that graphs with bounded max cut form closed family graphs. Given arbitrarily graph $G$ that doesn't contain $H$ as a minor, how to find max cut approximately.



The relevant topic can be found on On the complexity of the Maximum Cut problem Chapter 6. Graphs with bounded treewidth. The PTAS begins with making modification to the tree decomposition without increasing it's treewidth.

1) $T$ is a binary tree.

2) If a node $i \in I$ has two children $j_{1}$ and $j_{2}$, then $X_{i}=X_{j1}=X_{j2}$.

3) If a node $i \in I$ has one child $j$, then either $X_{j} \subset X_{i}$ and $|X_{i}-X_{j}|=1$, or $X_{i} \subset X_{j}$ and $|X_{j}-X_{i}|=1$.

In my opinion it's very strong modification, and actually I don't get the idea behind this modification. On the 2th condition if I understood rigth, if there is a node with two neighbors then all of then contain actually the same set of the vertexes, but what for?

  • 2
    $\begingroup$ it sounds like you're now asking another question. If the answers given thus far satisfy you, maybe you should mark one of them and ask a new question. Also, a link to the paper you're referring to would be helpful $\endgroup$ Jan 30, 2012 at 21:25
  • 1
    $\begingroup$ Also, $\epsilon \ne \in$. $\endgroup$
    – Jeffε
    Jan 31, 2012 at 2:14

2 Answers 2


MaxCut can be solved in polynomial time in $K_5$-minor-free graphs but is NP-hard in $K_6$-minor-free graphs (in particular, for apex graphs of planar graphs) [Barahona 1983].

See also this WG 2010 paper and slides by Marcin Kamiński.

  • $\begingroup$ Thanks for the answer. The paper contains reference to another paper by Hans L. Bodlaender and Klaus Jansen. On the complexity of the maximum cut problem. Which is actually elaborate this issue much better $\endgroup$
    – com
    Jan 29, 2012 at 20:18

There is a PTAS for H-minor-free classes of graphs that follows from the paper Algorithmic graph minor theory: Decomposition, approximation, and coloring by Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken-ichi Kawarabayashi in FOCS 2005.

  • $\begingroup$ Thanks for the answer. Unfortunately I didn't find PTAS for maximization problem. I took the paper from here Algorithmic graph minor theory. It has topic 3.2 on minimization schema, but maximization schema comes without the proof $\endgroup$
    – com
    Jan 29, 2012 at 20:15

Your Answer

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

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