Aravind, N.R. and Kalyanasundaram, Subrahmanyam and Kare, Anjeneya Swami
(2021)
Vertex partitioning problems on graphs with bounded tree width.
Discrete Applied Mathematics.
ISSN 0166218X
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. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an HFREE COLORING if none of the color classes contain H as an induced subgraph. The HFREE CHROMATIC NUMBER of G is the minimum number of colors required for an HFREE COLORING of G. Both The MATCHING CUT problem and the HFREE COLORING 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. The dependency of f(φ,t) on φ can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for MATCHING CUT problem and HFREE COLORING problem, parameterized by the treewidth of G. The single exponential FPT algorithm for the MATCHING CUT problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of Hfree coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G.
[error in script]
Actions (login required)

View Item 