Showing 2026Show all
2 papers · 1 filter
cs.DS2026
Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
Paweł Rafał Bieliński, Marta Piecyk, Paweł Rzążewski
The complexity of classical computational problems in graph classes defined by forbidding induced subgraphs is one of the central topics of algorithmic graph theory. Recently, ther…
cs.DS2026
A Complexity Dichotomy for Edge Subdivision to -Free Graphs
Marta Piecyk, R. B. Sandeep
For a fixed graph , \HFS\ asks whether at most edge subdivisions can make an input graph contain no induced copy of . We establish a complexity dichotomy for every fixed…