Tag: 김은정

We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers $s,t\in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$, with probability $2^{-\mathrm{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph.
The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems:
(1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17],
(2) a number of weighted variants of classic directed cut problems, such as Weighted st-Cut, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT.
By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the List H-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.

Joint work with Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström.

The Weighted $\mathcal{F}$-Vertex Deletion for a class $\mathcal{F}$ of graphs asks, given a weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in \mathcal{F}$. The case when $\mathcal{F}$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal{F}$-Vertex Deletion. Only three cases of minor-closed $\mathcal{F}$ are known to admit constant-factor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set.

We study the problem for the class $\mathcal{F}$ of ${\theta }_c$-minor-free graphs, under the equivalent setting of the Weighted c-Bond Cover, and present a constant-factor approximation algorithm using the primal-dual method. For this, we leverage a structure theorem implicit in [Joret et al., SIDMA’14] which states the following: any graph $G$ containing a ${\theta }_c$-minor-model either contains a large two-terminal protrusion, or contains a constant-size ${\theta }_c$-minor-model, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal{F}$-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families.

This is joint work with Euiwoong Lee and Dimitrios M. Thilikos.

We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s,t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t.

More precisely, we consider problems where an (unknown) solution is a set $Z\subseteq E(G)$ of size at most $k$ such that

• in $G-Z$, $s$ and $t$ are indistinct connected components,
• every edge of $Z$ connects two distinct connected components of $G-Z$, and
• if we define the set $Z_{s,t}\subseteq Z$ as these edges $e\in Z$ for which there exists an (s, t)-path P_e with $E(P_e)\cap Z=\{e\}$, then $Z_{s,t}$ separates s from t.

We prove that in the above scenario one can in randomized time $k^O(1)(|V(G)|+|E(G)|)$ add a number of edges to the graph so that with $2^{O(k\log k)}$ probability no added edge connects two components of $G-Z$ and $Z_{s,t}$ becomes a minimum cut between $s$ and $t$.

This additional property becomes a handy lever in applications. For example, consider the question of an $(s,t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s,t)$-cut in G. Hence, we immediately obtain that the aforementioned problem admits an $2^{O(k\log k)}{n}^O(1)$-time randomized fixed-parameter algorithm.

We apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below), and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal.

In fact, we go one step further. To demonstrate the power of the approach, we consider more generally the Boolean Min CSP(Γ)-problems, a.k.a. Min SAT(Γ), parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint (u → v), and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class, except those that explicitly encompass directed graph cuts.

This is a joint work with Stefan Kratsch, Marcin Pilipczuk and Magnus Wahlström.

Inspired by a width invariant defined on permutations by Guillemot and Marx [SODA ’14], we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, $K_t$-free unit $d$-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes (except map graphs without geometric embedding) we show how to compute in polynomial time a sequence of $d$-contractions, witness that the twin-width is at most $d$. We show that FO model checking, that is deciding if a given first-order formula $\varphi$ evaluates to true for a given binary structure $G$ on a domain $D$, is FPT in $|\varphi |$ on classes of bounded twin-width, provided the witness is given. More precisely, being given a $d$-contraction sequence for $G$, our algorithm runs in time $f(d,|\varphi |)\cdot |D|$ where $f$ is a computable but non-elementary function. We also prove that bounded twin-width is preserved by FO interpretations and transductions (allowing operations such as squaring or complementing a graph). This unifies and significantly extends the knowledge on fixed-parameter tractability of FO model checking on non-monotone classes, such as the FPT algorithm on bounded-width posets by Gajarský et al. [FOCS ’15].

In order to explore the limits of twin-width, we generalize to bounded twin-width classes a result by Norine et al. [JCTB ’06] stating that proper minor-free classes are small (i.e., they contain at most $n!c^n$ graphs on $n$ vertices, for some constant $c$). This implies by a counting argument that bounded-degree graphs, interval graphs, and unit disk graphs have unbounded twin-width.

Joint work with Stéphan Thomassé, Édouard Bonnet, and Rémi Watrigant.