On the parameterized complexity of the acyclic matching problem
From MaRDI portal
Publication:6038700
DOI10.1016/J.TCS.2023.113862arXiv2109.06004OpenAlexW4362673250MaRDI QIDQ6038700FDOQ6038700
Authors: Sahab Hajebi, Ramin Javadi 
Publication date: 2 May 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
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).
Full work available at URL: https://arxiv.org/abs/2109.06004
Recommendations
computational complexitytreewidthinduced matchingparameterized complexityacyclic matchingmodular-width
Cites Work
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph structure and monadic second-order logic. A language-theoretic approach
- Title not available (Why is that?)
- Color-coding
- Parameterized algorithms
- Characterizations of derived graphs
- Some results on graphs without long induced paths
- Induced matchings
- Treewidth. Computations and approximations
- On maximum induced matchings in bipartite graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Parameterized Algorithms for Modular-Width
- The parameterized complexity of the induced matching problem
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- NP-completeness of some generalizations of the maximum matching problem
- 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
- Title not available (Why is that?)
- New results on induced matchings
- Branching and Treewidth Based Exact Algorithms
- Induced matchings in intersection graphs.
- Finding a maximum induced matching in weakly chordal graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Bipartite Domination and Simultaneous Matroid Covers
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- On two geometric problems related to the travelling salesman problem
- Generalized subgraph-restricted matchings in graphs
- Parameterized complexity of finding subgraphs with hereditary properties.
- Parameterized complexity of induced graph matching on claw-free graphs
- Planarity of iterated line graphs
- Asymptotic bounds for some bipartite graph: Complete graph Ramsey numbers
- Simple upper bounds for partition functions
- Irredundancy in circular arc graphs
- The complexity of irredundant sets parameterized by size
- On the tree-width of even-hole-free graphs
- On the induced matching problem in Hamiltonian bipartite graphs
- Ramsey numbers and bipartite Ramsey numbers via quasi-random graphs
- Degenerate matchings and edge colorings
- Acyclic matching in some subclasses of graphs
- Acyclic matchings in subclasses of bipartite graphs
- Approximating maximum acyclic matchings by greedy and local search strategies
- On some hard and some tractable cases of the maximum acyclic matching problem
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)
