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

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

Benjamin Bergougnoux^♣, Charis Papadopoulos^F and Jan Arne Telle^♣.

Bergen Friday Seminar, October 9, 2020

♣University of Bergen, Norway

FUniversity of Ioannina, Greece

The parameters

Treewidth

I Unbounded in any dense graph class.

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

Divide a graph

Recursively decomposeyour graph into simplecuts.

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

G

Divide a graph

Recursively decomposeyour graph into simplecuts.

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

Different notions ofsimplicity= differentwidth measures.

Divide a graph

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

G

Divide a graph

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

G G

G G

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

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

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

Computation

I NP-hard for all these widths measures.

I Efficient approximation algorithms for tree-widthand rank-width.

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

I Tough open question formim-width.

The problem

Feedback Vertex Set

Feedback Vertex Set

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

X

Subset Feedback Vertex Set

Subset Feedback Vertex Set

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

S

X

Subset Feedback Vertex Set

Subset Feedback Vertex Set

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

S

Subset FVS is harder

Corneil and Fonlupt 1988

FVS is solvable inpolynomialtime on split graphs.

Fomin, Heggernes, Kratsch, Papadopoulos, Villanger. 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 2020

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

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(mim2) given a decomposition.

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(rw3)·n^O(1).

Same results holds forNode Multiway Cut.

Our Approach

S-forest

Minimum Subset FVS Complement: S-forest

S-forest

Minimum Subset FVS Complement_↓: forest

Casual dynamic programming

G

Combine and Reduce

S1 S2

S

Combination Reduction

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

Reduce

Lemma

For each cut(A, B), it is sufficient to keepn^O(mim2) 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(mim2)

Corollary

Subset FVS is solvable in time n^O(mim2) given a decomposition.

How we reduce: big picture

B

A

Partial solution Complement solution

We design aset of indicesof size n^O(mim2), each index is associated with somepartial and complement solutions.

Lemma

For everysolution F, there existsan index associated withF ∩A andF ∩B.

How we reduce: big picture

Lemma

For everysolution F, there existsan index associated withF ∩A andF ∩B.

We define anequivalence relationon the partial solutions associated with an indexi ofmim^O(mim) equivalence classes.

Lemma

IfX andW areequivalent for ithen for every complement solution Y: X∪Y is an S-forest iffW ∪Y is anS-forest.

⇒It is sufficient to keep n^O(mim2) partial solutions.

2-Neighbor equivalence

Definition

X,W ⊆Aare 2-neighbor equivalent overA if N(X)∩B =N(W)∩B and...

B

X W A

1 2⁺

nec2(A) := number of equivalence classesoverA.

Lemma

For everyA⊆V(G), have nec₂(A)≤n^2mim(A).

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

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 Y_↓

X_↓

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 Y_↓

X_↓

Small vertex cover

Lemma [B. and Kanté 2019]

Every induced forest betweenA andB have avertex cover of size4mim whose vertices havedifferent neighborhoods.

A B Y_↓

X_↓

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(mim2).

A B

X_↓ Y_↓

i ^{X\V C}

Index association

We associate each index with somepartial solutions and complements solutions.

A B

X_↓ i ^{X\V C}

Index association

We associate each index with somepartial solutions and complements solutions.

Y \V C

A B Y_↓

i

Why 2-neighbor equivalence?

BAD GOOOD

Index association

Lemma

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

A B

F∩A_↓ F∩B_↓

i

Lemma

For everyX andY associated withi,X∪Y induces anS-forest iff thecontractionof X∪Y inducesa forest.

Equivalence relation

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-equivalentthen for everyY ⊆B associated with i,G[X∪Y]is an S-forest iffG[W ∪Y]is anS-forest.

Result

Lemma

The number of partial solutions we keep is at most (nec₂(A) +nec₂(B))^O(mim2)mim^O(mim) ≤n^O(mim2)

Theorem

Subset FVS is solvable in time n^O(mim2) given a decomposition.

We have nec2(A)≤2^O(rw2) and mim≤rw Theorem

Subset FVS is solvable in time 2^O(rw3)·n^O(1).

Node Multiway Cut

X

T

Theorem

Node Multiway Cutis solvable in time 2^O(rw3) andn^O(mim2) given a decomposition.

Node Multiway Cut

T

Theorem

Node Multiway Cutis solvable in time 2^O(rw3) andn^O(mim2) given a decomposition.

Node Multiway Cut

X

T

S

Theorem

Node Multiway Cutis solvable in time 2^O(rw3) andn^O(mim2) given a decomposition.

Node Multiway Cut

T

S

Theorem

Node Multiway Cutis solvable in time 2^O(rw3) andn^O(mim2) given a decomposition.

Conclusion

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

Pattern

FVS, Dominating Set, Vertex Cover, Independent Set,... + connected and

acyclic variants SFVS, NMC

2^O(tw)·n^O(1) tw^O(tw)·n^O(1)

2^O(cw)·n^O(1) 2^O(rw2)·n^O(1)

n^O(mim)

2^O(cw2)·n^O(1)

n^O(mim2) 2^O(rw3)·n^O(1) ETH

optimal

Open questions

I Subset Odd Cycle Transversal?

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?

Thank you!