Imagen de Portada

The Complexity of Contracting Bipartite Graphs into Small Cycles

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Krithika, R., Sharma, Roohani, Tale, Prafullkumar
Formato:	Preprint
Publicado:	2022
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
por: Krithika, R., et al.
Publicado: (2023)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
por: Tale, Prafullkumar
Publicado: (2025)

Balanced Substructures in Bicolored Graphs
por: Ardra, P. S., et al.
Publicado: (2024)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
por: Foucaud, Florent, et al.
Publicado: (2023)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
por: Foucaud, Florent, et al.
Publicado: (2024)

Revisiting Path Contraction and Cycle Contraction
por: Krithika, R., et al.
Publicado: (2024)

The Parameterized Complexity of Computing the VC-Dimension
por: Foucaud, Florent, et al.
Publicado: (2025)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
por: Chakraborty, Dipayan, et al.
Publicado: (2024)

A Single Exponential-Time FPT Algorithm for Cactus Contraction
por: Krithika, R., et al.
Publicado: (2025)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
por: Gaikwad, Ajinkya, et al.
Publicado: (2025)

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

A Finer View of the Parameterized Landscape of Labeled Graph Contractions
por: Mathur, Yashaswini, et al.
Publicado: (2025)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
por: Gupta, Chetan, et al.
Publicado: (2025)

On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
por: Molkaraie, Mehdi
Publicado: (2025)

Geometric Bipartite Matching is in NC
por: Bhore, Sujoy, et al.
Publicado: (2024)

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

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
por: Lucke, Felicia
Publicado: (2025)

Monotone Contractions
por: Batziou, Eleni, et al.
Publicado: (2024)

On the Complexity of Nucleolus Computation for Bipartite b-Matching Games
por: Koenemann, Jochen, et al.
Publicado: (2021)

The Computational Complexity of Factored Graphs
por: Gupta, Shreya, et al.
Publicado: (2024)

The Parameterized Landscape of Labeled Graph Contractions
por: Lafond, Manuel, et al.
Publicado: (2025)

On the Complexity of Problems on Tree-structured Graphs
por: Bodlaender, Hans L., et al.
Publicado: (2022)

The Parameterized Complexity of Coloring Mixed Graphs
por: Lauerbach, Antonio, et al.
Publicado: (2026)

Hexasort -- The Complexity of Stacking Colors on Graphs
por: Klocker, Linus, et al.
Publicado: (2026)

On the Complexity of Vertex-Splitting Into an Interval Graph
por: Abu-Khzam, Faisal N., et al.
Publicado: (2026)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
por: Kocurek, Nicholas, et al.
Publicado: (2026)

Double Exponential Lower Bound for Telephone Broadcast
por: Tale, Prafullkumar
Publicado: (2024)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
por: Lokshtanov, Daniel, et al.
Publicado: (2024)

Bipartite Matching is in Catalytic Logspace
por: Agarwala, Aryan, et al.
Publicado: (2025)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
por: Liu, Brian, et al.
Publicado: (2024)

On the Parameterized Complexity of Semitotal Domination on Graph Classes
por: Retschmeier, Lukas
Publicado: (2025)

On the Structure of Hamiltonian Graphs with Small Independence Number
por: Jedličková, Nikola, et al.
Publicado: (2024)

On the Complexity of Bipartite Degree Realizability
por: Miklós, István
Publicado: (2025)

Linking Bipartiteness and Inversion in Algebra via Graph‐Theoretic Methods and Simulink
por: Mohammad Mazyad Hazzazi, et al.
Publicado: (2025)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
por: Komarath, Balagopal, et al.
Publicado: (2025)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
por: Janzer, Oliver, et al.
Publicado: (2024)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
por: Chen, Kean, et al.
Publicado: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
por: Hörsch, Florian, et al.
Publicado: (2025)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
por: Derakhshan, Mahsa, et al.
Publicado: (2025)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
por: D'Amico-Wong, Luca, et al.
Publicado: (2024)