On the complexity of solution extension of optimization problems
type: Item
instance of: scholarly article
title: On the complexity of solution extension of optimization problems
author: Katrin Casel
author: Henning Fernau
author: Mehdi Khosravian Ghadikolaei
author: Jérôme Monnot
author: Florian Sikora
published in: Theoretical Computer Science
publication date: 2022-02-01T00:00:00Z
full work available at URL: https://arxiv.org/abs/1810.04553
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7467463
zbMATH Keywords: extension problems
zbMATH Keywords: NP-hardness
zbMATH Keywords: parameterized complexity
MaRDI profile type: Publication
OpenAlex ID: W3209430198
cites work: Computational Complexity
cites work: Domination chain: characterisation, classical complexity, parameterised complexity and approximability
cites work: The many facets of upper domination
cites work: Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling
cites work: Q4535012
cites work: Dual subimplicants of positive Boolean functions
cites work: Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
cites work: Synchronizing words and monoid factorization: a parameterized perspective
cites work: Extension of some edge graph problems: standard and parameterized complexity
cites work: Extension of Vertex Cover and Independent Set in some classes of graphs
cites work: On product covering in 3-tier supply chain models: natural complete problems for W[3] and W[4]
cites work: Parameterized Algorithms
cites work: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
cites work: Fundamentals of parameterized complexity
cites work: Q4808679
cites work: Q5208373
cites work: Q4198056
cites work: Extension and its price for the Connected Vertex Cover problem
cites work: Enumerating minimal dominating sets in chordal bipartite graphs
cites work: Minimal dominating sets in interval graphs and trees
cites work: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets
cites work: Theoretical computer science. Introduction to automata, computability, complexity, algorithmics, randomization, communication, and cryptography.
cites work: Which problems have strongly exponential complexity?
cites work: Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs
cites work: A Polynomial Delay Algorithm for Enumerating Minimal Dominating Sets in Chordal Graphs
cites work: Reducibility among Combinatorial Problems
cites work: On enumerating minimal dicuts and strongly connected subgraphs
cites work: On the Complexity of Some Enumeration Problems for Matroids
cites work: A special planar satisfiability problem and a consequence of its NP- completeness
cites work: Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms
cites work: A Minimax Theorem for Directed Graphs
cites work: Q5226843
cites work: On cliques in graphs
cites work: On enumerating all minimal solutions of feedback problems
cites work: On feedback vertex sets and nonseparating independent sets in cubic graphs
cites work: Q5207888
DOI: 10.1016/J.TCS.2021.10.017
description: scientific article; zbMATH DE number 7467463