On the parameterized complexity of the acyclic matching problem
From MaRDI portal
Publication:6038700
Abstract: A matching is a set of edges in a graph with no common endpoint. A matching M is called acyclic if the induced subgraph on the endpoints of the edges in M is acyclic. Given a graph G and an integer k, Acyclic Matching Problem seeks for an acyclic matching of size k in G. The problem is known to be NP-complete. In this paper, we investigate the complexity of the problem in different aspects. First, we prove that the problem remains NP-complete for the class of planar bipartite graphs of maximum degree three and arbitrarily large girth. Also, the problem remains NP-complete for the class of planar line graphs with maximum degree four. Moreover, we study the parameterized complexity of the problem. In particular, we prove that the problem is W[1]-hard on bipartite graphs with respect to the parameter k. On the other hand, the problem is fixed parameter tractable with respect to the parameters tw and (k, c4), where tw and c4 are the treewidth and the number of cycles with length 4 of the input graph. We also prove that the problem is fixed parameter tractable with respect to the parameter k for the line graphs and every proper minor-closed class of graphs (including planar graphs).
Recommendations
Cites work
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1420901 (Why is no real title available?)
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Acyclic matching in some subclasses of graphs
- Acyclic matchings in subclasses of bipartite graphs
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Approximating maximum acyclic matchings by greedy and local search strategies
- Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
- Bipartite Domination and Simultaneous Matroid Covers
- Branching and Treewidth Based Exact Algorithms
- Characterizations of derived graphs
- Color-coding
- Degenerate matchings and edge colorings
- Finding a maximum induced matching in weakly chordal graphs
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- Generalized subgraph-restricted matchings in graphs
- Graph structure and monadic second-order logic. A language-theoretic approach
- Induced matchings
- Induced matchings in intersection graphs.
- Irredundancy in circular arc graphs
- NP-completeness of some generalizations of the maximum matching problem
- New results on induced matchings
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- On maximum induced matchings in bipartite graphs
- On some hard and some tractable cases of the maximum acyclic matching problem
- On the induced matching problem in Hamiltonian bipartite graphs
- On the tree-width of even-hole-free graphs
- On two geometric problems related to the travelling salesman problem
- Parameterized Algorithms for Modular-Width
- Parameterized algorithms
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized complexity of induced graph matching on claw-free graphs
- Planarity of iterated line graphs
- Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
- Simple upper bounds for partition functions
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Some results on graphs without long induced paths
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- The complexity of irredundant sets parameterized by size
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The parameterized complexity of the induced matching problem
- Treewidth. Computations and approximations
Cited in
(6)- Parameterized complexity of conflict-free matchings and paths
- On the complexity of minimum maximal acyclic matchings
- Parameterized Results on Acyclic Matchings with Implications for Related Problems
- Minimum maximal acyclic matching in proper interval graphs
- Parameterized complexity of perfectly matched sets
- Parameterized results on acyclic matchings with implications for related problems
This page was built for publication: On the parameterized complexity of the acyclic matching problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038700)
