NDLI: Parameterized Complexity of Discrete Morse Theory

Content Provider	ACM Digital Library
Author	Lewiner, Thomas Paixão, João Spreer, Jonathan Burton, Benjamin A.
Copyright Year	2016
Description	Author Affiliation: Department of Mathematics, Pontifícia Universidade Católica, Rio de Janeiro, Brazil(Spreer, Jonathan; School of mathematics and physics, The University of Queensland, Brisbane, Australia (Burton, Benjamin A.; Paixo, Joo); Lewiner, Thomas)
Abstract	Optimal Morse matchings reveal essential structures of cell complexes that lead to powerful tools to study discrete geometrical objects, in particular, discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand, we prove that the erasability problem is $\textit{W}[\textit{P}]-complete$ on the natural parameter. On the other hand, we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds, which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplices. This algorithm also shows fixed-parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we discuss the topological significance of the chosen parameters and investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds.
Starting Page	1
Ending Page	24
Page Count	24
File Format	PDF
ISSN	00983500
e-ISSN	15577295
DOI	10.1145/2738034
Volume Number	42
Issue Number	1
Journal	ACM Transactions on Mathematical Software (TOMS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-03-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	$\textit{W}[\textit{P}]-completeness$ Alternating cycle-free matching Collapsibility Computational topology Discrete Morse theory Erasability Fixed-parameter tractability Parameterized complexity Treewidth
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Parameterized complexity of discrete morse theory

Fixed-parameter tractability of anonymizing data by suppressing entries

Fixed-parameter tractability and parameterized complexity, applied to problems from computational social choice (2008)

Fixed-Parameter Algorithms For Protein Similarity Search Under mRNA Structure Constraints

Parameterized computational complexity of Dodgson and Young elections (2007)

Invitation to Fixed-Parameter Algorithms

Bounded fixed-parameter tractability and reducibility (2007).

Bounded Fixed-Parameter Tractability and Reducibility (2006)

Fixed-parameter tractability and completeness ii: completeness for w[1]. Theoretical computer science a 141 (1995).

Parameterized Complexity of Discrete Morse Theory

Similar Documents

Parameterized complexity of discrete morse theory

Fixed-parameter tractability of anonymizing data by suppressing entries

Fixed-parameter tractability and parameterized complexity, applied to problems from computational social choice (2008)

Fixed-Parameter Algorithms For Protein Similarity Search Under mRNA Structure Constraints

Parameterized computational complexity of Dodgson and Young elections (2007)

Invitation to Fixed-Parameter Algorithms

Bounded fixed-parameter tractability and reducibility (2007).

Bounded Fixed-Parameter Tractability and Reducibility (2006)

Fixed-parameter tractability and completeness ii: completeness for w[1]. Theoretical computer science a 141 (1995).

Parameterized Complexity of Discrete Morse Theory