Reducing rank of the adjacency matrix by graph modification

DOI10.1016/j.tcs.2016.02.020zbMath1353.05117OpenAlexW2287500156MaRDI QIDQ344771

Saket Saurabh, Pranabendu Misra, Syed M. Meesum

Publication date: 24 November 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.02.020

zbMATH Keywords

parameterized complexityfixed parameter tractableedge editinggraph modificationrank of adjacency matrixvertex deletion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A survey of parameterized algorithms and the complexity of edge modification ⋮ Parameterized low-rank binary matrix approximation ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Rank reduction of oriented graphs by vertex and edge deletions

Cites Work

• Finding odd cycle transversals.
• Fixed-parameter algorithms for cluster vertex deletion
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• The maximum edge biclique problem is NP-complete
• Cluster graph modification problems
• Graph minors. XIII: The disjoint paths problem
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• NP-completeness results for edge modification problems
• Editing Simple Graphs
• Chordal Editing is Fixed-Parameter Tractable
• Extremal Combinatorics
• A More Effective Linear Kernelization for Cluster Editing
• The rank and size of graphs
• Interval Deletion Is Fixed-Parameter Tractable
• Node-and edge-deletion NP-complete problems
• Subexponential Parameterized Algorithm for Minimum Fill-In