Minimum Violation Vertex Maps and Their Applications to Cut Problems

DOI10.1137/19M1290899zbMath1453.05072OpenAlexW3094217343MaRDI QIDQ5138968

Chao Xu, Ken-ichi Kawarabayashi

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

optimizationgraph homomorphismgraph cut

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of surjective homomorphism problems-a survey
• An algebraic hardness criterion for surjective constraint satisfaction.
• Blocking optimal arborescences
• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• Blocking unions of arborescences
• Parameterized complexity of length-bounded cuts and multicuts
• The computational complexity of disconnected cut and \(2 K_2\)-partition
• Beating the 2-approximation factor for global bicut
• A dichotomy for minimum cost graph homomorphisms
• Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation
• Approximation of Minimum Cost Homomorphisms
• Absolute Retracts and Varieties of Reflexive Graphs
• The Complexity of Finite-Valued CSPs
• Length-bounded cuts and flows
• Skew Bisubmodularity and Valued CSPs
• LP Relaxation and Tree Packing for Minimum $k$-Cut
• The approximability of MAX CSP with fixed-value constraints
• Approximation algorithms for classification problems with pairwise relationships
• Approximation Algorithms for Graph Homomorphism Problems
• Diameter increase caused by edge deletion
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Approximating Multicut and the Demand Graph
• Multiway cuts in directed and node weighted graphs
• The complexity of finding maximum disjoint paths with length constraints
• The Dichotomy of Minimum Cost Homomorphism Problems for Digraphs
• Testing the Complexity of a Valued CSP Language
• Improved Hardness for Cut, Interdiction, and Firefighter Problems
• The Karger-Stein algorithm is optimal for k-cut
• The Complexity of Boolean Surjective General-Valued CSPs
• The number of minimum k -cuts: improving the Karger-Stein bound
• The Approximability of Three-valued MAX CSP
• The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
• Discrete convexity and polynomial solvability in minimum 0-extension problems

This page was built for publication: Minimum Violation Vertex Maps and Their Applications to Cut Problems