Parameterized algorithms for finding square roots

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

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

Publication date: 29 March 2016

Published in: Algorithmica (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• Complexity of finding graph roots with girth conditions
• Computing square roots of trivially perfect and threshold graphs
• Parametrized complexity theory.
• Sparse Square Roots
• Bipartite roots of graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Title not available (Why is that?)
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs
• Uniqueness of graph square roots of girth six
• The square root of a graph
• Title not available (Why is that?)
• On cliques in graphs
• Solving MAX-\(r\)-SAT above a tight lower bound
• The square of a block graph

Cited In (11)

• Strong triadic closure in cographs and graphs of low maximum degree
• Title not available (Why is that?)
• Finding cactus roots in polynomial time
• Maximizing the strong triadic closure in split graphs and proper interval graphs
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Graph square roots of small distance from degree one graphs
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• A square root algorithm
• Finding cut-vertices in the square roots of a graph
• Finding Cactus Roots in Polynomial Time

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)