User Tools
Sidebar
Table of Contents
Max Cut on almost planar graphs
People: Christine Dahn
Definition
Given an edge-weighted graph G, the NP-hard Max-Cut problem asks for a node bipartition such that the sum of edge weights joining the different partitions is maximized. In the example on the right (resp. above) a maximum cut with value 7 is shown. The color of the nodes indicates on which side of the bipartition, defining the cut, a node is. (Red-curvy edges belong to the cut; black-straight edges do not belong to the cut.)
Idea
Our initial motivation was to develop a Max Cut algorithm on graphs with only a few crossings. The main idea of all developed algorithms is to remove the crossings from the graph one by one, to use a planar Max Cut algorithm to compute the solution. Since, by removing a crossing, part of the solution space is cut off, we need to consider more than one variant of removing a crossing to guarantee the optimal solution. Thereby we parameterize the problem depending on the number of crossings in a given embedding resp. the crossing number of the given graph.
Development
Hence, we developed a series of algorithms on almost planar graphs, i.e., graphs with only a few crossings. Starting with a FPT Max Cut algorithm on (embedded) 1-planar graphs, i.e., graphs which can be drawn in the plane with at most one crossing per edge, we continuously improved the runtime dependency on the number of crossings k from 4^k [1] to 3^k [2,3]. Finally, we were able to drop the assumption of 1-planarity and expanded the FPT Max Cut algorithm to general graphs [4]. Furthermore, we could strengthen the parameter from the number of crossings in a given embedding to the crossing number, improving the runtime dependency on the crossing number k to 2^k [4].
Example: FPT Max-Cut on 1-planar graphs [3]
Exemplary, we look at the crossing on the left of the above graph. The algorithm removes the crossing in the three ways: by removing the edge bd (slide 2), by merging the nodes b and c (slide 4), and by merging the nodes c and d (slide 6). For the resulting graphs the algorithm is called recursively. The recursively calculated cuts of the three graphs are shown in slide 3,5 and 7 of the animation above, with the last showing the largest cut. This cut is transferred back to the original graph by splitting the contracted node (slide 8). The resulting maximum cut has a cut value of 17. The color of the nodes indicates on which side of the bipartition, defining the cut, a node is. All unweighted edges have weight 1. (Red-curvy edges belong to the cut; black-straight edges do not belong to the cut.)
Example: Max-Cut parameterized by crossing number [4]
With this approach we look at each crossing individually. To be able to remove the crossing from the graph without interfering with the other crossings, we separate it from the other crossings. Therefore, the two crossing edges are bisubdivided at v resp. x (slide 2), i.e., two new nodes are inserted on each edge, so the crossing lies between the four new nodes. Furthermore, the curvy edges are added to the set of fixed cut edges. Now we have two cases: either v and x are on the same side of the partition (slide 3) or on opposite sides (slide 5). In the first case we identify v' with x' (slide 4). In the second case we identify x' with w' (slide 6). Hereby the crossing is removed in both cases, while retaining the partition property. The node coloring gives a partition of the nodes, that is induced by the newly added fixed cut edges. (Dashed or dotted edges show examples of other edges in the graph.)
Publications
- [1] Christine Dahn, Entwicklung eines MAX-CUT-Algorithmus für fast-planare Graphen. Master Thesis, TU Dortmund (September 2017).
- [2] Christine Dahn, Nils M. Kriege, Petra Mutzel. A Fixed-Parameter Algorithm for the Max-Cut Problem on Embedded 1-Planar Graphs.
In: Iliopoulos C., Leong H., Sung WK. (eds) Combinatorial Algorithms. IWOCA 2018. Lecture Notes in Computer Science, vol 10979. Springer, Cham (2018). (arxiv)
- [3] Christine Dahn, Nils M. Kriege, Petra Mutzel, Julian Schilling: Fixed-parameter algorithms for the weighted Max-Cut problem on embedded 1-planar graphs.
Theoretical Computer Science 852: 172-184 (2021). (arxiv)
- [4] Markus Chimani, Christine Dahn, Martina Juhnke-Kubitzke, Nils M. Kriege, Petra Mutzel, Alexander Nover:Maximum Cut Parameterized by Crossing Number.
Journal of Graph Algorithms and Applications 24(3): 155-170 (2020). (arxiv)