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

CC BY-SA 3.0
2012-01-29T20:15:04.837Z
Thanks for the answer. Unfortunately I didn't find PTAS for maximization problem. I took the paper from here [Algorithmic graph minor theory](http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf). It has topic 3.2 on minimization schema, but maximization schema comes without the proof
com
CC BY-SA 3.0
2012-01-29T14:01:16.660Z
2012-01-29T14:01:16.660Z
Marcin Kamiński
<p>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) [<a href="http://www.sciencedirect.com/science/article/pii/0167637783900160">Barahona 1983</a>].</p>

<p>See also <a href="http://rutcor.rutgers.edu/~mkaminski/preprints/Max-Cut%20and%20containment%20relations%20in%20graphs.pdf">this WG 2010 paper</a> and <a href="http://rutcor.rutgers.edu/~mkaminski/slides/Max-Cut%20and%20containment%20relations%20in%20graphs.pdf">slides</a> by <a href="http://rutcor.rutgers.edu/~mkaminski/research.html">Marcin Kamiński</a>.</p>

CC BY-SA 3.0
2012-01-29T20:18:38.587Z
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
com
CC BY-SA 3.0
2012-01-28T15:48:03.210Z
2012-01-28T16:34:03.200Z
2012-01-28T16:34:03.200Z
Jeffε
<p>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.</p>

<p>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.</p>

<p>Thanks!</p>

<p><strong>Addendum:</strong></p>

<p>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.</p>

<p>1) $T$ is a binary  tree.</p>

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

<p>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$.</p>

<p>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?  </p>

CC BY-SA 3.0
2012-01-30T21:25:23.887Z
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
Suresh Venkat
CC BY-SA 3.0
2012-01-31T02:14:31.167Z
Also, $\epsilon \ne \in$.
Jeffε
<graph-algorithms>
Max-Cut Of Minor Closed Family
com
# Max-Cut Of Minor Closed Family

(Asked by: username_0 on 2012-01-28)

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.

Thanks!

**Addendum:**

The relevant topic can be found on On the username_0plexity of the Maximum Cut problem Chapter 6. Graphs with bounded treewidth. The PTAS begins with making modification to the tree deusername_0position 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?

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: 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  
> **username_2**: Also, $\epsilon \ne \in$.  

---

## 2 answers

### Answer by username_2 on 2012-01-28. Score: 16 | Accepted answer

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](http://www.sciencedirect.username_0/science/article/pii/0167637783900160)].

See also [this WG 2010 paper](http://rutcor.rutgers.edu/~mkaminski/preprints/Max-Cut%20and%20containment%20relations%20in%20graphs.pdf) and [slides](http://rutcor.rutgers.edu/~mkaminski/slides/Max-Cut%20and%20containment%20relations%20in%20graphs.pdf) by [username_3](http://rutcor.rutgers.edu/~mkaminski/research.html).

> **Comments:**
> **username_0**: Thanks for the answer. The paper contains reference to another paper by Hans L. Bodlaender and Klaus Jansen. On the username_0plexity of the maximum cut problem. Which is actually elaborate this issue much better  

---

### Answer by username_3 on 2012-01-29. Score: 9

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

> **Comments:**
> **username_0**: Thanks for the answer. Unfortunately I didn't find PTAS for maximization problem. I took the paper from here [Algorithmic graph minor theory](http://www-math.mit.edu/~hajiagha/graphminoralgorithm.pdf). It has topic 3.2 on minimization schema, but maximization schema username_0es without the proof  

---

