On Structural Parameterizations of the Matching Cut Problem

N R, Aravind and Kalyanasundaram, Subrahmanyam and Kare, A S (2017) On Structural Parameterizations of the Matching Cut Problem. In: International Conference on Combinatorial Optimization and Applications, December 16-18, 2017, China.

Full text not available from this repository. (Request a copy)


In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The matching cut problem is the problem of deciding whether a given graph has a matching cut. The matching cut problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f(ϕ,t)nO(1), where ϕ is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. In [Theoretical Computer Science, 2016], Kratsch and Le asked to give a single exponential algorithm for the matching cut problem with tree-width alone as the parameter. We answer this question by giving a 2O(t)nO(1) time algorithm. We also show the tractability of the matching cut problem when parameterized by neighborhood diversity and other structural parameters.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Matching cut, Decomposable graphs, Parameterized algorithm
Subjects: Computer science
Computer science > Algorithm Analysis
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 13 Dec 2017 04:07
Last Modified: 13 Dec 2017 05:08
URI: http://raiith.iith.ac.in/id/eprint/3699
Publisher URL: https://doi.org/10.1007/978-3-319-71147-8_34
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 3699 Statistics for this ePrint Item