Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width

(1)

Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width

Benjamin Bergougnoux^?, Charis Papadopoulos^† and Jan Arne Telle^?.

WG 2020, June 26, 2020

?University of Bergen, Norway

†University of Ioannina, Greece

(2)

The parameters

(3)

Treewidth

I Unbounded in any dense graph class.

I Tractability results on dense graph classes can be explained with rank-width andmim-width.

(4)

Divide a graph

Recursively decomposeyour graph...

G

(5)

Divide a graph

Recursively decomposeyour graph... intosimplecuts.

→We describe the simplicityof a cut with afunction f: cut→Q.

Different notions ofsimplicity= differentwidth measures.

(6)

Divide a graph

Width of a decompositionD:= max f(cut)among the cutsofD.

G

(7)

Divide a graph

Width of a graphG:= min width of a decomposition ofG.

G G

(8)

Rank-width

Defined from the function rw(A, B) := therank of adjacency matrixbetween A andB overGF(2).

B

A





1 0 1 0 1 1 1 1 0



rw

=2

(9)

Maximum Induced Matching width (mim-width)

Defined from the function mim(A, B) := the size of a maximum induced matching in the bipartite graph betweenAand B.

B

A

(10)

Hierarchy

Cographs, hereditary distance Interval, permutation, k-polygon, Dilworth-k,

convex graphs,...

MSO ₁

tree-width clique-width

rank-width

mim-width (σ, ρ)-Dominating Set problems

MSO ₂

Modeling Power Meta-algorithmic

applications

Tree, partialk-tree

(11)

Computation complexity

I NP-hard for all these widths measures.

I Efficient algorithms for tree-width andrank-width.

→ Running time: 2^O(k)·n^O(1).

I Tough open question formim-width.

(12)

The problem

(13)

Feedback Vertex Set

Find a set of verticesX of minimum weighthittingall cycles (G−X is a forest).

X

(14)

Subset Feedback Vertex Set

Find a set of verticesX of minimum weight hitting all cycles going throughaprescribed set of verticesS.

S

X

(15)

Subset Feedback Vertex Set

Find a set of verticesX of minimum weight hitting all cycles going throughaprescribed set of verticesS.

S

(16)

Subset FVS is harder

Corneil and Fonlupt 1988

FVS is solvable inpolynomialtime on split graphs.

Fomin et al. 2014

Subset FVS isNP-hard on split graphs.

Bodalender, Cygan, Kratsch and Nederlof 2015 FVS is solvable in time 2^O(tw)·n.

B., Bonnet, Brettell and Kwon [ArxiV]

Subset FVS can not be solved in time 2^o(tw^log^tw)·n^O(1) unless ETH fails.

(17)

Recent results

Papadopoulos and Tzimas 2019

Subset FVS is solvable inpolynomialtime on interval graphs and permutation graphs.

Jaffke, Kwon and Telle 2019 | B. and Kanté 2019 FVS is solvable in time n^O(mim) given a decomposition.

Our result

Subset FVS is solvable in time n^O(mim²⁾ given a decomposition.

(18)

Algorithmic consequences

Corollary

Subset FVS is solvable inpolynomial time oninterval, permutation, bi-interval graphs, circular arc and circular permutation graphs, convex graphs,k-polygon, Dilworth-kand co-k-degenerate graphs for fixedk.

Theorem

Subset FVS is solvable in time 2^O(rw³⁾·n^O(1).

Same results holds for Node Multiway Cut.

(19)

Our Approach

(20)

Neighbor equivalence

Definition

X,Y ⊆A are1-neighbor equivalent overAif N(X)∩B=N(Y)∩B.

nec₁(A) :=number of equivalence classes overA.

B

X Y A

Lemma

For everyA⊆V(G), have nec2(A)≤n^O(mim).

(21)

Reduce

Lemma

It is sufficient to keep for each cut (A, B)

(nec₂(A) +nec₂(B))Ô(mim)·mimÔ(mim)≤nÔ(mim²⁾ partial solutions.

Set of partial solutions

C ⊆2^A

Reduce

D ⊆ C small and equivalent

toC

∀Y⊆B, best(C,Y) =best(D,Y)

|D| ≤n^O(mim²⁾

Corollary

(22)

S-forest

Minimum

Subset FVS

Complement:

S

-forest

(23)

S-forest

Minimum

Subset FVS

Complement

_↓

: forest

(24)

S-forest −→ forest

Lemma

We can contract the components ofG[X]−S andunions of the components ofG[Y]−S such that the resulting graph is aforest.

A B

X Y

(25)

Lemma

A B Y_↓

X_↓

(26)

Lemma

A B Y_↓

X_↓

(27)

Small vertex cover

Lemma [B. and Kanté 2019]

After contractions, every induced forest between A andB have a vertex cover of size 4mimwhose vertices have different

neighborhoods.

A B Y_↓

X_↓

(28)

Indices

Definition

An indexiis a collection of at most4mim+ 1representatives for the2-neighbor equivalence overA andB.

Number of indices≤(nec₂(A) +nec₂(B))^O(mim)≤n^O(mim²⁾.

A B

X_↓ Y_↓

i ^X^\^{V C}

(29)

Index association

We associate each index with somepartial solutions and some subsets ofB.

A B

X_↓ i ^X^\^{V C}

(30)

We associate each index with somepartial solutions and some subsets ofB.

Y \V C

A B Y_↓

i

(31)

Lemma

For everysolution F, there exists anindexisuch thatF∩A and F∩B are associated withi.

A B

F ∩A_↓ F ∩B_↓

i

(32)

Definition

Twopartial solutions X, W associated withiare i-equivalentif they connectthe vertices of the vertex coverin the same way.

Number ofi-equivalence classes≤mim^O(mim)

Lemma

IfX andW arei-equivalent, then for everyY ⊆B associated with i,G[X∪Y]is a solution iff G[W ∪Y]is also a solution.

(33)

Result

Lemma

It is sufficient to keep, for every indexi, a partial solutions of maximum weightfor eachi-equivalence class.

The number of partial solutions we keep is at most (nec₂(A) +nec₂(B))Ô(mim²⁾mimÔ(mim) ≤nÔ(mim²⁾

Theorem

(34)

Algorithmic consequences

We have nec₂(A)≤2^O(rw²⁾ and mim≤rw Lemma

It is sufficient to keep, for every indexi, a partial solutions of maximum weightfor eachi-equivalence class.

The number of partial solutions we keep is at most (nec₂(A) +nec₂(B))Ô(mim²⁾mimÔ(mim) ≤2Ô(rw³⁾

Theorem

Subset FVS is solvable in time 2^O(rw³⁾·n^O(1).

(35)

Node Multiway Cut

X T

Theorem

Node Multiway Cutis solvable in time 2^O(rw³⁾ andn^O(mim²⁾ given a decomposition.

(36)

T

Theorem

(37)

X T

S

Theorem

(38)

Neighbor equivalence relations

These relations have been usedfor many problems:

I (σ, ρ)-Dominating Setproblems [Bui-Xuan, Telle and Vatshelle 2013]

I Their connected and acyclic variants and Max Cut [B. and Kanté 2019]

I Subset FVS and Node Multiway Cut [B., Papadapoulos and Telle]

for many parameters: tree-width, clique-width, rank-width, Q-rank-width,mim-width

(39)

Open questions

I Can we characterizewhich problems are in XP parameterized by themim-width of a given decomposition?

B. and Kanté 2019

Theconnected and acyclic variants of(σ, ρ)-Dominating Set problems are solvable in timen^O(mim) given a decomposition.

I Can we approximate/compute themim-width of a graph in XP-time?

I Can we recognize the graphs ofmim-width one?

(40)

Casual dynamic programming

G

(41)

Combine and Reduce

S1 S2

S

Combination Reduction

{X₁∪X₂|X₁∈ S₁, X₂∈ S₂}

(42)

Reduce: tough and key step

In general

If it is enough to keep N partial solutions at each step, then we can solve the problem in timeN^O(1)·n^O(1).

Node Multiway Cut and Subset Feedback Vertex Set on Graphs of Bounded Mim-width