Minimum violation vertex maps and their applications to cut problems

DOI10.1137/19M1290899MaRDI QIDQ5138968zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Chao Xu

Publication date 4 December 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/19m1290899

zbMATH Keywords

graph cutgraph homomorphismoptimization

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• The vertex \(k\)-cut problem
• The complexity of multicut and mixed multicut problems in (di)graphs
• scientific article; zbMATH DE number 3876616
• On cutting a few vertices from a graph
• Minimax inverse problems of minimum cuts

Cites work

• A dichotomy for minimum cost graph homomorphisms
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Absolute Retracts and Varieties of Reflexive Graphs
• An algebraic hardness criterion for surjective constraint satisfaction.
• Approximating multicut and the demand graph
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Approximation Algorithms for Graph Homomorphism Problems
• Approximation algorithms for the 0-extension problem
• Approximation of minimum cost homomorphisms
• Beating the 2-approximation factor for global bicut
• Beyond Boolean surjective VCSPs
• Blocking unions of arborescences
• Cutting up is hard to do: the parameterised complexity of k-cut and related problems
• Diameter increase caused by edge deletion
• Discrete convexity and polynomial solvability in minimum 0-extension problems
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• scientific article; zbMATH DE number 6850401 (Why is no real title available?)
• scientific article; zbMATH DE number 742985 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 7561584 (Why is no real title available?)
• Improved hardness for cut, interdiction, and firefighter problems
• Length-bounded cuts and flows
• LP relaxation and tree packing for minimum k-cut
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Multiway cuts in directed and node weighted graphs
• On the Structure of Polynomial Time Reducibility
• Parameterized complexity of length-bounded cuts and multicuts
• Skew bisubmodularity and valued CSPs
• Surjective \texttt{H}-colouring over reflexive digraphs
• Testing the Complexity of a Valued CSP Language
• The approximability of MAX CSP with fixed-value constraints
• The Approximability of Three-valued MAX CSP
• The Complexity of Boolean Surjective General-Valued CSPs
• The complexity of finding maximum disjoint paths with length constraints
• The Complexity of Multiterminal Cuts
• The complexity of surjective homomorphism problems-a survey
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The dichotomy of minimum cost homomorphism problems for digraphs
• The Karger-Stein algorithm is optimal for k-cut
• The minimum k-way cut of bounded size is fixed-parameter tractable
• The number of minimum k-cuts: improving the Karger-Stein bound

This page was built for publication: Minimum violation vertex maps and their applications to cut problems

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