Showing 2024Show all
2 papers · 1 filter
cs.DS2024
Sparse induced subgraphs in -free graphs of bounded clique number
Maria Chudnovsky, Jadwiga Czyżewska, Kacper Kluk +2
Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the larges…
math.CO2024
Graph Reconstruction with Connectivity Queries
Kacper Kluk, Hoang La, Marta Piecyk
We study a problem of reconstruction of connected graphs where the input gives all subsets of size k that induce a connected subgraph. Originally introduced by Bastide et al. (WG 2…