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 1618, 2017, China.
Full text not available from this repository.
(
Request a copy)
Abstract
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 secondorder logic (MSOL) formula and hence is solvable in linear time for graphs with bounded treewidth. However, this approach leads to a running time of f(ϕ,t)nO(1), where ϕ
is the length of the MSOL formula, t is the treewidth 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 treewidth 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]
Actions (login required)

View Item 