betaFeedback

WorksComputer Science

Important Cuts with Logical Constraints: A Meta-Theorem for Eulerian Digraphs

Abstract

Important separators are a standard tool in parameterized cut algorithms. An SS-TT separator is important if it is inclusion-wise minimal and no separator of at most the same size leaves a strict superset of the vertices reachable from SS after deletion. Their use relies on a boundedness theorem: for fixed kk, the number of important SS-TT separators of size at most kk is at most a constant (4k4^k to be precise) independent of the input size, even in directed graphs, and they can be enumerated efficiently. The classical theory, however, controls only the size of the separator, not the structure of the source side cut off by it. Once the source side is required to satisfy a condition such as acyclicity, bipartiteness, or another logical property, the corresponding maximal source sides can be unbounded in general digraphs. This obstruction is fundamentally related to hardness phenomena in directed deletion problems such as Directed Odd Cycle Transversal}. Prior to this work, even in undirected graphs, boundedness of such maximal constrained source sides was known only in more specialized settings, not at the level of generality considered in our work.

Paper details

vlnc:W_2uded7c6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…