Half-integrality, LP-branching, and FPT Algorithms
From MaRDI portal
Publication:2816829
DOI10.1137/140962838zbMath1343.05151OpenAlexW2570081448MaRDI QIDQ2816829
Yuichi Yoshida, Yoichi Iwata, Magnus Wahlström
Publication date: 26 August 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/140962838
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (33)
Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ On a general framework for network representability in discrete optimization ⋮ A compact representation for minimizers of \(k\)-submodular functions ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Odd cycle transversal in mixed graphs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ Neighborhood persistency of the linear optimization relaxation of integer linear optimization ⋮ Unnamed Item ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ The Complexity of Valued CSPs ⋮ Edge bipartization faster than \(2^k\) ⋮ Finding temporal paths under waiting time constraints ⋮ Multi-Budgeted Directed Cuts ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ Linear kernels and linear-time algorithms for finding large cuts ⋮ An improved FPT algorithm for independent feedback vertex set ⋮ Approximability of clique transversal in perfect graphs ⋮ Discrete Convex Functions on Graphs and Their Algorithmic Applications ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Computing subset transversals in \(H\)-free graphs ⋮ Faster graph bipartization ⋮ On $k$-Submodular Relaxation ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ A Compact Representation for Minimizers of k-Submodular Functions (Extended Abstract) ⋮ Unnamed Item ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Multi-budgeted directed cuts ⋮ On group feedback vertex set parameterized by the size of the cutset ⋮ Parametric bisubmodular function minimization and its associated signed ring family
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On group feedback vertex set parameterized by the size of the cutset
- Generalized roof duality and bisubmodular functions
- FPT algorithms for path-transversal and cycle-transversal problems
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Strong computational lower bounds via parameterized complexity
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Packing non-zero \(A\)-paths in group-labelled graphs
- An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
- The expressive power of binary submodular functions
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Constraints, consistency and closure
- Multimatroids. IV: Chain-group representations
- Characterising tractable constraints
- Multimatroids. II: Orthogonality, minors and connectivity
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- Which problems have strongly exponential complexity?
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Packing non-returning A-paths
- Packing non-returning \(A\)-paths algorithmically
- Non-zero disjoint cycles in highly connected group labelled graphs
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Tight lower bounds for certain parameterized NP-hard problems
- Packing $A$-Paths in Group-Labelled Graphs via Linear Matroid Parity
- On Multiway Cut Parameterized above Lower Bounds
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Towards Minimizing k-Submodular Functions
- Min CSP on Four Elements: Moving beyond Submodularity
- The Complexity of Finite-Valued CSPs
- Designing FPT Algorithms for Cut Problems Using Randomized Contractions
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- On the power of unique 2-prover 1-round games
- On the structure of all minimum cuts in a network and applications
- Vertex packings: Structural properties and algorithms
- Multimatroids I. Coverings by Independent Sets
- Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
- Multiway cuts in node weighted graphs
- Faster Parameterized Algorithms Using Linear Programming
- Coverings and delta-coverings
- Representative Sets and Irrelevant Vertices
- Submodular Function Minimization under Covering Constraints
- The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization
- Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
- Linear-Time FPT Algorithms via Network Flow
- Half-integrality, LP-branching and FPT Algorithms
- Bisubmodular Function Minimization
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Multimatroids. III: Tightness and fundamental graphs
This page was built for publication: Half-integrality, LP-branching, and FPT Algorithms
