Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs

AI-generated keywords: Weighted Max-Cut Problem

AI-generated Key Points

The license of the paper does not allow us to build upon its content and the key points are generated using the paper metadata rather than the full article.

  • The paper proposes two fixed-parameter tractable algorithms to solve the weighted Max-Cut problem on embedded 1-planar graphs.
  • A graph is considered 1-planar if it can be drawn in the plane with at most one crossing per edge.
  • The proposed algorithms are parameterized by the crossing number k of the given embedding and recursively reduce a 1-planar graph to at most 3^k planar graphs using edge removal and node contraction techniques.
  • Their main algorithm then solves the Max-Cut problem for these planar graphs using FCE-MaxCut, which was introduced by Liers and Pardella [21].
  • In case of non-negative edge weights, they suggest a variant that allows solving planar instances with any planar Max-Cut algorithm.
  • The authors demonstrate that a maximum cut in a given 1-planar graph can be derived from solutions for its corresponding planar graphs.
  • Their algorithms compute a maximum cut in an embedded weighted 1-planar graph with n nodes and k edge crossings in time O(3^kn^{3/2} log n).
  • This work is an extension of their conference version (available as arXiv:1803.10983), which is currently under review at TCS.
  • The proposed algorithms have significant implications for real world applications such as network design and optimization problems where finding a maximum cut in a graph is crucial.
Also access our AI generated: Comprehensive summary, Lay summary, Blog-like article; or ask questions about this paper to our AI assistant.

Authors: Christine Dahn, Nils M. Kriege, Petra Mutzel, Julian Schilling

This work is an extension of the conference version arXiv:1803.10983 , currently under review at TCS
License: CC BY-NC-ND 4.0

Abstract: We propose two fixed-parameter tractable algorithms for the weighted Max-Cut problem on embedded 1-planar graphs parameterized by the crossing number k of the given embedding. A graph is called 1-planar if it can be drawn in the plane with at most one crossing per edge. Our algorithms recursively reduce a 1-planar graph to at most 3^k planar graphs, using edge removal and node contraction. Our main algorithm then solves the Max-Cut problem for the planar graphs using the FCE-MaxCut introduced by Liers and Pardella [21]. In the case of non-negative edge weights, we suggest a variant that allows to solve the planar instances with any planar Max-Cut algorithm. We show that a maximum cut in the given 1-planar graph can be derived from the solutions for the planar graphs. Our algorithms compute a maximum cut in an embedded weighted 1-planar graph with n nodes and k edge crossings in time O(3^k n^{3/2} log n).

Submitted to arXiv on 29 Nov. 2018

Ask questions about this paper to our AI assistant

You can also chat with multiple papers at once here.

The license of the paper does not allow us to build upon its content and the AI assistant only knows about the paper metadata rather than the full article.

AI assistant instructions?

Results of the summarizing process for the arXiv paper: 1812.03074v1

This paper's license doesn't allow us to build upon its content and the summarizing process is here made with the paper's metadata rather than the article.

In their paper titled "Fixed-Parameter Algorithms for the Weighted Max-Cut Problem on Embedded 1-Planar Graphs," Christine Dahn, Nils M. Kriege, Petra Mutzel, and Julian Schilling propose two fixed-parameter tractable algorithms to solve the weighted Max-Cut problem on embedded 1-planar graphs. A graph is considered 1-planar if it can be drawn in the plane with at most one crossing per edge. The proposed algorithms are parameterized by the crossing number k of the given embedding and recursively reduce a 1-planar graph to at most 3^k planar graphs using edge removal and node contraction techniques. Their main algorithm then solves the Max-Cut problem for these planar graphs using FCE-MaxCut, which was introduced by Liers and Pardella [21]. In case of non-negative edge weights, they suggest a variant that allows solving planar instances with any planar Max-Cut algorithm. The authors demonstrate that a maximum cut in a given 1-planar graph can be derived from solutions for its corresponding planar graphs. Their algorithms compute a maximum cut in an embedded weighted 1-planar graph with n nodes and k edge crossings in time O(3^kn^{3/2} log n). This work is an extension of their conference version (available as arXiv:1803.10983), which is currently under review at TCS. The proposed algorithms have significant implications for real world applications such as network design and optimization problems where finding a maximum cut in a graph is crucial.
Created on 01 May. 2023

Assess the quality of the AI-generated content by voting

Score: 0

Why do we need votes?

Votes are used to determine whether we need to re-run our summarizing tools. If the count reaches -10, our tools can be restarted.

Similar papers summarized with our AI tools

Navigate through even more similar papers through a

tree representation

Look for similar papers (in beta version)

By clicking on the button above, our algorithm will scan all papers in our database to find the closest based on the contents of the full papers and not just on metadata. Please note that it only works for papers that we have generated summaries for and you can rerun it from time to time to get a more accurate result while our database grows.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.