Finding a maximum induced degenerate subgraph faster than 2ⁿ

DOI10.1007/978-3-642-33293-7_3MaRDI QIDQ4899236zbMATH OpenOpenAlexFDO

Authors Marcin Pilipczuk, Michał Pilipczuk

Publication date 7 January 2013

Published in Parameterized and Exact Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Abstract: In this paper we study the problem of finding a maximum induced d-degenerate subgraph in a given n-vertex graph from the point of view of exact algorithms. We show that for any fixed d one can find a maximum induced d-degenerate subgraph in randomized (2-eps_d)^n n^O(1) time, for some constant eps_d>0 depending only on d. Moreover, our algorithm can be used to sample inclusion-wise maximal induced d-degenerate subgraphs in such a manner that every such subgraph is output with probability at least (2-eps_d)^-n; hence, we prove that their number is bounded by (2-eps_d)^n.

Recommendations

• Faster Subgraph Counting in Sparse Graphs
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Large induced degenerate subgraphs
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph

Cited in

(16)

• Large induced degenerate subgraphs
• On the number of connected sets in bounded degree graphs
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Subexponential-time algorithms for finding large induced sparse subgraphs
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Faster exact algorithms for some terminal set problems
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Efficient enumeration of induced subtrees in a K-degenerate graph
• On subgraphs of bounded degeneracy in hypergraphs
• Largest chordal and interval subgraphs faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Faster Subgraph Counting in Sparse Graphs
• Bicriteria \textsf{FPT}-approximation algorithms for vertex deletion to bounded degeneracy graphs
• Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity
• A note on large degenerate induced subgraphs in sparse graphs
• Bicriteria FPT-approximation algorithms for vertex deletion to bounded degeneracy graphs

This page was built for publication: Finding a maximum induced degenerate subgraph faster than \(2^{n}\)

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