Buchumschlag

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Gaikwad, Ajinkya, Kumar, Hitendra, Maity, Soumen, Saurabh, Saket, Sharma, Roohani
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parameterized Algorithms for Editing to Uniform Cluster Graph
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2026)

Balanced Substructures in Bicolored Graphs
von: Ardra, P. S., et al.
Veröffentlicht: (2024)

The Complexity of Contracting Bipartite Graphs into Small Cycles
von: Krithika, R., et al.
Veröffentlicht: (2022)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

From FPT Decision to FPT Enumeration
von: Creignou, Nadia, et al.
Veröffentlicht: (2025)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
von: Agrawal, Akanksha, et al.
Veröffentlicht: (2024)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
von: Yi, Yongming
Veröffentlicht: (2026)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
von: Bhaskar, Umang, et al.
Veröffentlicht: (2025)

The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth
von: Schestag, Jannik, et al.
Veröffentlicht: (2026)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2026)

The Complexity of Min-Max Optimization with Product Constraints
von: Bernasconi, Martino, et al.
Veröffentlicht: (2026)

Parameterized Max Min Feedback Vertex Set
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

Constructive Separations and Their Consequences
von: Chen, Lijie, et al.
Veröffentlicht: (2022)

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
von: Bernasconi, Martino, et al.
Veröffentlicht: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
von: Jackson, Andrew
Veröffentlicht: (2025)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
von: Czégel, András, et al.
Veröffentlicht: (2025)

MaxMin-RLHF: Alignment with Diverse Human Preferences
von: Chakraborty, Souradip, et al.
Veröffentlicht: (2024)

Linear Equations with Min and Max Operators: Computational Complexity
von: Chatterjee, Krishnendu, et al.
Veröffentlicht: (2024)

Separations in Proof Complexity and TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2022)

Constructive Separations from Gate Elimination
von: Carmosino, Marco, et al.
Veröffentlicht: (2026)

Improved Circuit Lower Bounds and Quantum-Classical Separations
von: Grewal, Sabee, et al.
Veröffentlicht: (2024)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
von: Grigorescu, Elena, et al.
Veröffentlicht: (2025)

Separations between Combinatorial Measures for Transitive Functions
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2021)

Second-Order Min-Max Optimization with Lazy Hessians
von: Chen, Lesi, et al.
Veröffentlicht: (2024)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
Veröffentlicht: (2025)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
von: Bhattacharjee, Sutanay, et al.
Veröffentlicht: (2026)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
von: Samar, Sahil, et al.
Veröffentlicht: (2026)

FPT Parameterisations of Fractional and Generalised Hypertree Width
von: Lanzinger, Matthias, et al.
Veröffentlicht: (2025)

Separations above TFNP from Sherali-Adams Lower Bounds
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Symport/Antiport P Systems with Membrane Separation Characterize P^(#P)
von: Ducros, Vivien, et al.
Veröffentlicht: (2025)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
von: Çivril, Ali
Veröffentlicht: (2021)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
von: Bhattacharya, Sreejata Kishor, et al.
Veröffentlicht: (2024)

Higher Hardness Results for the Reconfiguration of Odd Matchings
von: Dorfer, Joseph
Veröffentlicht: (2026)

On (In)approximability of MaxMin Independent Set Reconfiguration
von: Hoang, Hung P., et al.
Veröffentlicht: (2026)

On the Parameterized Complexity of Min-Sum-Radii
von: Kumar, Pankaj, et al.
Veröffentlicht: (2026)

Baby PIH: Parameterized Inapproximability of Min CSP
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)