Cover Image

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Oum, Sang-il, Sokołowski, Marek
Format:	Preprint
Published:	2026
Subjects:	Combinatorics Data Structures and Algorithms 05C85, 68R05
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Branch-width of represented matroids in matrix multiplication time
by: Choi, Mujin, et al.
Published: (2026)

Branch-width of connectivity functions is fixed-parameter tractable
by: Korhonen, Tuukka, et al.
Published: (2026)

On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction
by: Onofri, Elia
Published: (2024)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs
by: Galby, Esther, et al.
Published: (2024)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

Obstructions to Erdős-Pósa Dualities for Minors
by: Paul, Christophe, et al.
Published: (2024)

Zero-free regions of partition functions with applications to algorithms and graph limits
by: Regts, Guus
Published: (2015)

$t$-sails and sparse hereditary classes of unbounded tree-width
by: Cocks, Daniel
Published: (2023)

Temporalizing digraphs via linear-size balanced bi-trees
by: Bessy, Stéphane, et al.
Published: (2023)

Reconfiguration of Independent Transversals
by: Buys, Pjotr, et al.
Published: (2024)

Colorful Minors
by: Protopapas, Evangelos, et al.
Published: (2025)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

On the joint embedding property for cographs and trees
by: Carter, Daniel
Published: (2024)

Optimal Adjacency Labels for Subgraphs of Cartesian Products
by: Esperet, Louis, et al.
Published: (2022)

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
by: Milanič, Martin, et al.
Published: (2024)

A $5/4$-Approximation for Two-Edge Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2024)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
by: Nasre, Meghana, et al.
Published: (2023)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
by: Agrawal, Akanksha, et al.
Published: (2024)

A New Construction of the Vietoris-Rips Complex
by: Rieser, Antonio
Published: (2023)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
by: Liao, I-Cheng, et al.
Published: (2023)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
by: Jelínek, Vít, et al.
Published: (2020)

Pathographs and some (un)decidability results
by: Carter, Daniel, et al.
Published: (2025)

Conformal Hypergraphs: Duality and Implications for the Upper Clique Transversal Problem
by: Boros, Endre, et al.
Published: (2023)

Finding irrelevant vertices in linear time on bounded-genus graphs
by: Golovach, Petr A., et al.
Published: (2019)

Young domination on Hamming rectangles
by: Gravner, Janko, et al.
Published: (2025)

Tight bounds on adjacency labels for monotone graph classes
by: Bonnet, Édouard, et al.
Published: (2023)

Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
by: Bonnet, Édouard, et al.
Published: (2023)

A practical algorithm for 2-admissibility
by: Awofeso, Christine, et al.
Published: (2025)

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
by: Chiu, Yung-Chung, et al.
Published: (2021)

Faster parameterized algorithms for modification problems to minor-closed classes
by: Morelle, Laure, et al.
Published: (2022)

Vertex identification to a forest
by: Morelle, Laure, et al.
Published: (2024)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
by: Li, Xingfu, et al.
Published: (2026)

From Hop Reduction to Sparsification for Negative Length Shortest Paths
by: Quanrud, Kent, et al.
Published: (2025)