Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
DOI10.1007/s00453-018-0431-8zbMath1414.05128OpenAlexW2795452868MaRDI QIDQ1755775
Saket Saurabh, Fahad Panolan, Neeldhara Misra, Venkatesh Raman, Ashutosh Rai
Publication date: 11 January 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0431-8
perfect graphsco-chordal graphsmaximum induced subgraphspolynomial kernel lower boundsrandomized FPT algorithms
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Perfect graphs (05C17)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- Infeasibility of instance compression and succinct PCPs for NP
- Solving MAX-\(r\)-SAT above a tight lower bound
- Enumerating maximal independent sets with applications to graph colouring.
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
- On problems without polynomial kernels
- The maximum k-colorable subgraph problem for chordal graphs
- Improved FPT algorithms for weighted independent set in bull-free graphs
- A randomized polynomial kernel for subset feedback vertex set
- Parameterized complexity of finding subgraphs with hereditary properties.
- Faster parameterized algorithms for deletion to split graphs
- Efficient exact algorithms through enumerating maximal independent sets and other techniques
- Parametrized complexity theory.
- Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
- Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- (Meta) Kernelization
- Fourier meets M\"{o}bius: fast subset convolution
- Kernelization: New Upper and Lower Bound Techniques
- On graphs with polynomially solvable maximum-weight clique problem
- A New Algorithm for Generating All the Maximal Independent Sets
- Kernelization and Sparseness: the case of Dominating Set
- Maximum $r$-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds
- Compression via Matroids
- Kernelization Lower Bounds Through Colors and IDs
- Representative Sets and Irrelevant Vertices
- Bidimensionality and Geometric Graphs
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
This page was built for publication: Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
