Parameterized algorithms for finding square roots

DOI10.1007/S00453-014-9967-4zbMATH Open1332.05136OpenAlexW2111680439MaRDI QIDQ262249FDOQ262249

Authors Manfred Cochefert, Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma 

Publication date 29 March 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.5469

zbMATH Keywords

generalized kernelgraph square rootparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We show that the following two problems are fixed-parameter tractable with parameter k: testing whether a connected n-vertex graph with m edges has a square root with at most n-1+k edges and testing whether such a graph has a square root with at least m-k edges. Our first result implies that squares of graphs obtained from trees by adding at most k edges can be recognized in polynomial time for every fixed k>=0; previously this result was known only for k=0. Our second result is equivalent to stating that deciding whether a graph can be modified into a square root of itself by at most k edge deletions is fixed-parameter tractable with parameter k.

Recommendations

• A square root algorithm
• scientific article; zbMATH DE number 3864371
• An algorithm for inverse square-roots
• Algorithms for Square Roots of Graphs
• scientific article; zbMATH DE number 221539
• Dynamic properties of an exact algorithm for square root calculation
• An integer based square root algorithm

Cites work

• scientific article; zbMATH DE number 1248190 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A New Algorithm for Generating All the Maximal Independent Sets
• A good characterization of squares of strongly chordal split graphs
• Algorithms for Square Roots of Graphs
• Bipartite roots of graphs
• Complexity of finding graph roots with girth conditions
• Computing roots of graphs is hard
• Computing square roots of trivially perfect and threshold graphs
• Fundamentals of parameterized complexity
• Graph theory
• On cliques in graphs
• Parametrized complexity theory.
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Solving MAX-\(r\)-SAT above a tight lower bound
• Sparse square roots
• The square of a block graph
• The square root of a graph
• Uniqueness of graph square roots of girth six

Cited in

(13)

• Finding cut-vertices in the square roots of a graph
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Sparse square roots
• A linear kernel for finding square roots of almost planar graphs
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Finding cactus roots in polynomial time
• A linear kernel for finding square roots of almost planar graphs
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• A square root algorithm
• Finding cactus roots in polynomial time
• Strong triadic closure in cographs and graphs of low maximum degree
• Computing square roots of graphs with low maximum degree
• Graph square roots of small distance from degree one graphs

This page was built for publication: Parameterized algorithms for finding square roots

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q262249)