On the complexity of finding large odd induced subgraphs and odd colorings

DOI10.1007/s00453-021-00830-xOpenAlexW3006309500MaRDI QIDQ5918338

Rémy Belmonte, Ignasi Sau

Publication date: 26 July 2021

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

parameterized complexityexponential time hypothesisodd subgraphrank-widthodd coloringsingle-exponential algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Induced subgraphs of a tree with constraint degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• On weak odd domination and graph-based quantum secret sharing
• On the complexity of some colorful problems parameterized by treewidth
• Parameterized complexity of even/odd subgraph problems
• Boolean-width of graphs
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth
• On induced subgraphs with odd degrees
• Treewidth. Computations and approximations
• Which problems have strongly exponential complexity?
• Finding even subgraphs even faster
• Every tree contains a large induced subgraph with all degrees odd
• A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
• Rank-width: algorithmic and structural results
• Odd induced subgraphs in graphs with treewidth at most two
• XSAT and NAE-SAT of linear CNF classes
• Parameterized complexity of Eulerian deletion problems
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• Intractability of Clique-Width Parameterizations
• Large Induced Subgraphs with All Degrees Odd
• The intractability of computing the minimum distance of a code
• Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
• Clique-width III
• Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• MOD-2 INDEPENDENCE AND DOMINATION IN GRAPHS
• Connected odd dominating sets in graphs
• Parameterized Algorithms
• Slightly Superexponential Parameterized Problems
• On the complexity of \(k\)-SAT
• On induced subgraphs with all degree odd

This page was built for publication: On the complexity of finding large odd induced subgraphs and odd colorings