Half-Integrality, LP-Branching, and FPT Algorithms
Half-Integrality, LP-Branching,
and FPT Algorithms
“
FPT Algorithms via Discrete Relaxation”
Yuichi Yoshida
NII
Joint work with Yoichi Iwata and Magnus Wahlström
Fixed Parameter Tractability
FPT (fixed parameter tractability)
•
Introduce a parameter p (e.g., solution size)
•
A problem is
FPT
if can be solved in f(p)poly(n) time.
Many NP-hard problems
become
FPT for appropriate params:
•
Vertex cover, multiway cut, …
Many techniques for proving FPT:
•
Branching, important separator, color coding, iterative
compression, half-integrality, …
This talk
Introduce a unified technique to get FPT algorithms:
Discrete relaxation
•
Generalizes the branching method based on half-integrality
•
Many applications
•
Bisubmodularity and k-submodularity play a crucial role.
Motivating example: Vertex Cover a
bove LP
Vertex cover: vertex set
incident to every edge.
VC above LP
: Is there a vertex cover of size
≤ (LP value + p)?
•
Current best: O
*
(2.6181
p
)
[Narayanaswamy et al’13]
Branching guided by LP
Let’s look at a simple O
*
(4
p
)-time algorithm.
[Nemhauser-Trotter’75]
The LP above satisfy
•
Half-integrality
: a {0, ½, 1}-valued LP solution exists.•
Persistency
: For any LP solution
x
, one can fix integral
variables without changing the integer optimum.
min Σ
v
∈
V
x
v
s.t. x
u
+ x
v
≥ 1 (uv
∈
E)
0 ≤ x
v
≤ 1 (v
∈
V)
Branching guided by LP
Solve LP
LP value = 3.5
Branching guided by LP
For each branching, the LP value increases by at least ½
⇒
The size of the search tree is 2
2p
= 4
p
⇒
O
*
(4
p
)-time algorithm.
Pick a free variable v.
v
v
Analysis
Can we similarly show FPT of other problems?
•
Yes for (node) Multiway cut above LP. [Cygan et al.’13]
•
Not sure for other problems because it is hard to prove half-
integrality and persistency of LP relaxations.
Let’s design relaxations that are
inherently half-integral
!
Discrete relaxation
Original function f: D
V
→ℤ
+
Relaxed function f’: D’
V
→ℤ
+
/2 for D
⊆
D’.
D =
integral
part, D’ \ D =
fractional
part
We ask for f’ to satisfy:
•
Consistency
: f’(
x
) = f(
x
) for any
x
∈
D
V
.
•
Persistency
: For any solution
x
’ to f’, one can fix integral
variables without changing the optimum of f.
•
Tractability
: f’ can be efficiently minimized
FPT Algorithms via discrete relaxation
•
f
The algorithm and proof are the same as the LP-branching.
E.g.: VC above LP
•
Set D’ = {0, ½, 1} and f’ = LP (restricted to half-integralassignments).
•
f’ is consistent, persistent, and tractable because so is the LP.
⇒
O
*
(2
2p
) time
[Iwata-Wahlström-Y.’14]
f: D
V
→ℤ
+
has a consistent, persistent, and tractable relaxation
f’:D’
V
→ℤ
+
/2
⇒
f can be minimized in O
*
(|D|
2(min f – min f’)
) time.
Discrete relaxation and submodularity
Is this useful? Isn’t it just a rephrasing of LP relaxation?
Many problems admit consistent discrete relaxations that are
Bisubmodular
or
k-submodular
⇒
Persistency and tractability automatically follow.
Submodularity
A function f: {0, 1}V
→ ℝ is
submodular
if, for any
x
,
y
∈
{0, 1} V
,
f(
x
) + f(
y
) ≥ f(
x
∨
y
) + f(
x
∧
y
),
where
∨
and
∧
= coordinate-wise max and min.
•
Can be minimized in polynomial time.
[Iwata et al.
’01] [Schrijver’00]
Bisubmodularity
A function f: {0, ½, 1}V
→ ℝ is
bisubmodular
if
f(
x
) + f(
y
) ≥ f(
x
∨
y
) + f(
x
∧
y
)
for any
x
,
y
∈
{0, ½, 1}V
.
•
Can be minimized in polynomial time
[Fujishige-Iwata’05]
•
Persistent when D = {0, 1} [Kolmogorov’12]
Vertex cover
Original problem
(D = {0, 1})min f(
x
) := Σ
v
∈
E
x
v
+ M
×
Σ
uv
∈
E
max(0, 1 – x
u
– x
v
)
g(a, b) := max(0, 1 – a – b) is
not submodular
…
g(1, 0) + g(0, 1) < g(0, 0) + g(1, 1)
Vertex cover
Relaxed problem
(D’ = {0, 1/2
, 1})
min f’(
x
) := Σ
v
∈
E
x
v
+ M
×
Σ
uv
∈
E
max(0, 1 – x
u
– x
v
)
g’(a, b) := max(0, 1 – a – b) is now
bisubmodular
!
g(1
∨
0, 0
∨
1) = g(1
∧
0, 0
∧
1) = g(1/2, 1/2) = 0
⇒
The relaxed function f’ is also bisubmodular.
⇒
VC is solvable in O
*
(4
min f-min f’
) time.
⇒
As min f’ = LP value, VC above LP is solvable in O
*
(4
p
) time.
Other applications: binary
Boolean functions
Any binary function:
{0, 1}2
→ ℤ
+
can be relaxed to a half-integral
bisubmodular function
.
⇒
Any function f that is a sum of binary functions can be
minimized in O
*
(4
min f
) time.
–
Odd Cycle Transversal
–
Almost 2-SAT
Same time complexity as previous works, but the proof is
much simpler.
Other applications: Multiway Cut above LP
Multiway cut:
e
dge set separating all the terminals T = {t1
,…,t
k
}.
MC above LP: Is there a multiway cut of size ≤ (LP value + p)?
O
*
(4
p
)-time FPT based on LP-branching
[Cygan et al. 2012]
How can we prove this via discrete relaxation?
k-Submodularity
A function f: {0, 1, 2, …, k}V
→ ℝ is
k-submodular
if
f(
x
) + f(
y
) ≥ f(
x
∨
y
) + f(
x
∧
y
)
for any
x
,
y
∈
{0, 1, 2, …, k}V
.
•
No poly-time algorithm known in the value oracle model.
–
The sum of constant-arity k-submodular functions can be
minimized by LP.
[Thapper-
Živný‘13]
•
Persistent when D = {1, 2, …, k} [Kolmogorov’12]
2
0
1
k
…
Multiway Cut
and
k-submodularity
Original problem
(
D = {1, …, k})min f(
x
) := Σ
uv
∈
E
[x
u
≠ x
v
] s.t. x
ti
= i.
Multiway Cut
and
k-submodularity
Relaxed problem
(D’ = {0
, 1, …, k})
min f’(
x
) := Σ
uv
∈
E
[x
u
≠ x
v
] s.t. x
ti
= i.
Multiway Cut
and
k-submodularity
Relaxed problem
(D’ = {0
, 1, …, k})
min f’(
x
) := Σ
uv
∈
E
[x
u
≠ x
v
] s.t. x
ti
= i.
f’ is k-submodular!
⇒
MC can be solved in O
*
(k
2(min f-min f’)
) time.
⇒
As min f’ = LP value, MC above LP is solvable in O
*
(k
2p
) time.
⇒
A slightly careful analysis gives O
*
(2
2p
) = O
*
(4
p
) time.
Node Multiway Cut
Original problem
(D = {1, …, k, C}, C = remove the vertex)min f(
x
) := Σ
v
∈
V
g(x
v
) + M
×
Σ
uv
∈
E
h(x
u
, x
v
) s.t. x
ti
= i
•
No k-submodular relaxation…
Relaxation of Node Multiway Cut
Relaxed problem
(D’ = {1, …, k, C, 0, 1’, …, k’
})
min f’(
x
) := Σ
v
∈
V
g’(x
v
) + M
×
Σ
uv
∈
E
h’(x
u
, x
v
) s.t. x
ti
= i
Intuition
Relaxation of Node Multiway Cut
f’(
x
) + f’(
y
) ≥ f’(
x
∨
y
) + f’(
x
∧
y
) holds for any
x
,
y
∈
D’
V
where
•
Tractable because (
∨
,
∧
) is a binary symmetric fractional
polymorphism [Thapper-
Živný
’
13]
•
Persistency easily follows
Conclusion
Discrete relaxation
: a unified technique to
get
FPT algorithms.
•
If the relaxation admits some nice fractional polymorphism,
then we automatically achieve FPT.
Other results
•
Unique Label Cover: O
*
(k
2p
) time (k = domain size)
–
Previous best
: O
*
(k
O(p^
2log p)
)
[Chitnis et al.’12]
•
Group FVS: O
*
(4
p
) time
–
Works even when the group is exponentially large.
–
Previous best: O
*
(2
O(plog p)
)
[Cygan et al.’12])
•
L
inear-time
(= O(c
p
(n+m))) FPT
algorithms using max flow
for
VC above LP, Almost 2SAT, and Unique Label Cover.
Future work
•
Directed graph cut problems?
–
Directed FVS, Directed Multiway Cut, …
⇒
Magnus’ talk
•
Which VCSPs can be minimized on subdomain D
⊆
D’ in FPT time?
–
Any function f: {1,…,k}V
→ ℤ can be extended to a k-
submodular function f’: {0
,1,…,k}
V
→ ℚ [Hirai-Iwamasa’15]
–
But f’ can take a negative value even when f is non-
negative…
27
Multiway Cut
and
k-submodularity
Relaxed problem
(D’ = {0
, 1, …, |T|})
min f(
x
) := Σ
uv
∈
E
[x
u
≠ x
v
] s.t. x
ti
= i.
[a ≠ b] is |T|-submodular!
⇒
The relaxed function f’ is also |T|-submodular.
⇒
MC can be solved in O
*
(4
min f-min f’
)-time.
This talk introduces a unified technique for developing Fixed Parameter Tractability (FPT) algorithms through discrete relaxation and half-integrality. It explores various applications including Vertex Cover, Odd Cycle Transversal, Multiway Cut, and more. The talk delves into the concept of branching guided by LP solutions, demonstrating how FPT algorithms can be designed efficiently for NP-hard problems. Examples and analyses support the effectiveness of this approach in solving combinatorial optimization problems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Half-Integrality, LP-Branching, and FPT Algorithms FPT Algorithms via Discrete Relaxation Yuichi Yoshida NII Joint work with Yoichi Iwata and Magnus Wahlstr m
Fixed Parameter Tractability FPT (fixed parameter tractability) Introduce a parameter p (e.g., solution size) A problem is FPT if can be solved in f(p)poly(n) time. Many NP-hard problems become FPT for appropriate params: Vertex cover, multiway cut, Many techniques for proving FPT: Branching, important separator, color coding, iterative compression, half-integrality,
This talk Introduce a unified technique to get FPT algorithms: Discrete relaxation Generalizes the branching method based on half-integrality Many applications Vertex Cover (above LP) Odd Cycle Transversal Unique Label Cover Multiway Cut (above LP) (Group/Subset) Feedback Vertex Set Almost 2-SAT Bisubmodularity and k-submodularity play a crucial role.
Motivating example: Vertex Cover above LP Vertex cover: vertex set incident to every edge. VC above LP: Is there a vertex cover of size (LP value + p)? 0 1 1 1 1 1 1 0 0 0 0 LP = 3.5 OPT = 4 Current best: O*(2.6181p) [Narayanaswamy et al 13]
Branching guided by LP Let s look at a simple O*(4p)-time algorithm. min v Vxv s.t. xu+ xv 1 (uv E) 0 xv 1 (v V) [Nemhauser-Trotter 75] The LP above satisfy Half-integrality: a {0, , 1}-valued LP solution exists. Persistency: For any LP solution x, one can fix integral variables without changing the integer optimum.
Branching guided by LP Solve LP Fix integral values Check other variables can be fixed without increasing the LP value. 1 1 1 1 1 0 0 0 0 LP value = 3.5 LP value = 4 cannot fix Fixed to 1 Fixed to 0
Branching guided by LP Fixed to 1 Pick a free variable v. Fixed to 0 v v Branching For each branching, the LP value increases by at least The size of the search tree is 22p= 4p O*(4p)-time algorithm.
Analysis Can we similarly show FPT of other problems? Yes for (node) Multiway cut above LP. [Cygan et al. 13] Not sure for other problems because it is hard to prove half- integrality and persistency of LP relaxations. Let s design relaxations that are inherently half-integral!
Discrete relaxation Original function f: DV + Relaxed function f : D V +/2 for D D . D = integral part, D \ D = fractional part We ask for f to satisfy: Consistency: f (x) = f(x) for any x DV. Persistency: For any solution x to f , one can fix integral variables without changing the optimum of f. Tractability: f can be efficiently minimized
FPT Algorithms via discrete relaxation f [Iwata-Wahlstr m-Y. 14] f: DV +has a consistent, persistent, and tractable relaxation f :D V +/2 f can be minimized in O*(|D|2(min f min f )) time. The algorithm and proof are the same as the LP-branching. E.g.: VC above LP Set D = {0, , 1} and f = LP (restricted to half-integral assignments). f is consistent, persistent, and tractable because so is the LP. O*(22p) time
Discrete relaxation and submodularity Is this useful? Isn t it just a rephrasing of LP relaxation? Many problems admit consistent discrete relaxations that are Bisubmodular or k-submodular Persistency and tractability automatically follow.
Submodularity A function f: {0, 1}V is submodular if, for any x, y {0, 1} V, f(x) + f(y) f(x y) + f(x y), where and = coordinate-wise max and min. Can be minimized in polynomial time. [Iwata et al. 01] [Schrijver 00]
Bisubmodularity A function f: {0, , 1}V is bisubmodular if f(x) + f(y) f(x y) + f(x y) for any x, y {0, , 1}V. 0 1/ 2 0 1 0 1/ 2 1/ 2 1/ 2 1/ 2 1 1 0 0 0 1/ 2 1 0 0 1/ 2 1/ 2 1 1/ 2 1 0 1/ 2 1 1/ 2 1 1/ 2 1/ 2 Can be minimized in polynomial time [Fujishige-Iwata 05] Persistent when D = {0, 1} [Kolmogorov 12] 1/ 2 1
Vertex cover Original problem (D = {0, 1}) min f(x) := v Exv+ M uv Emax(0, 1 xu xv) g(a, b) := max(0, 1 a b) is not submodular g(1, 0) + g(0, 1) < g(0, 0) + g(1, 1)
Vertex cover Relaxed problem (D = {0, 1/2, 1}) min f (x) := v Exv+ M uv Emax(0, 1 xu xv) g (a, b) := max(0, 1 a b) is now bisubmodular! g(1 0, 0 1) = g(1 0, 0 1) = g(1/2, 1/2) = 0 The relaxed function f is also bisubmodular. VC is solvable in O*(4min f-min f ) time. As min f = LP value, VC above LP is solvable in O*(4p) time.
Other applications: binary Boolean functions Any binary function: {0, 1}2 +can be relaxed to a half-integral bisubmodular function. Any function f that is a sum of binary functions can be minimized in O*(4min f) time. Odd Cycle Transversal Almost 2-SAT Same time complexity as previous works, but the proof is much simpler.
Other applications: Multiway Cut above LP Multiway cut: edge set separating all the terminals T = {t1, ,tk}. MC above LP: Is there a multiway cut of size (LP value + p)? t2 t1 t3 O*(4p)-time FPT based on LP-branching [Cygan et al. 2012] How can we prove this via discrete relaxation?
k-Submodularity A function f: {0, 1, 2, , k}V is k-submodular if f(x) + f(y) f(x y) + f(x y) for any x, y {0, 1, 2, , k}V. 0 i j 0 i j 2 k 1 0 0 i j 0 0 0 0 i i i 0 i 0 i 0 0 j j 0 j j 0 0 j No poly-time algorithm known in the value oracle model. The sum of constant-arity k-submodular functions can be minimized by LP. [Thapper- ivn 13] Persistent when D = {1, 2, , k} [Kolmogorov 12]
Multiway Cut and k-submodularity Original problem (D = {1, , k}) min f(x) := uv E[xu xv] s.t. xti= i. t4 4 1 t3 t1 3 1 t2 2
Multiway Cut and k-submodularity Relaxed problem (D = {0, 1, , k}) min f (x) := uv E[xu xv] s.t. xti= i. t4 4 1 t3 t1 0 3 1 t2 2
Multiway Cut and k-submodularity Relaxed problem (D = {0, 1, , k}) min f (x) := uv E[xu xv] s.t. xti= i. f is k-submodular! MC can be solved in O*(k2(min f-min f )) time. As min f = LP value, MC above LP is solvable in O*(k2p) time. A slightly careful analysis gives O*(22p) = O*(4p) time.
Node Multiway Cut Original problem (D = {1, , k, C}, C = remove the vertex) min f(x) := v Vg(xv) + M uv Eh(xu, xv) s.t. xti= i h i j C g i 0 1 0 i 0 j 1 0 0 j 0 C 0 0 0 C 1 No k-submodular relaxation
Relaxation of Node Multiway Cut Relaxed problem (D = {1, , k, C, 0, 1 , , k }) min f (x) := v Vg (xv) + M uv Eh (xu, xv) s.t. xti= i g' h' i j C i' j 0 i 0 1 0 0 i 0 j 1 0 0 0 j 0 C 0 0 0 0 0 0 C 1 i 0 0 0 0 0 i j 0 0 0 0 0 j 0 0 0 0 0 0 0
Intuition t4 4 C C 4 t3 t1 0 3 3 1 1 2 C C t2 2
Relaxation of Node Multiway Cut f (x) + f (y) f (x y) + f (x y) holds for any x, y D Vwhere i j C i' j 0 i j C i' j 0 i i 0 i i i i i i 0 i i 0 0 j 0 j j j j j j 0 j j 0 j 0 C i j C C C C C i j C i j 0 i i j C i C i i i 0 i i 0 0 j i j C C j j j 0 j j 0 j 0 0 i j C i j 0 0 0 0 0 0 0 0 Tractable because ( , ) is a binary symmetric fractional polymorphism [Thapper- ivn 13] Persistency easily follows
Conclusion Discrete relaxation: a unified technique to get FPT algorithms. If the relaxation admits some nice fractional polymorphism, then we automatically achieve FPT. Other results Unique Label Cover: O*(k2p) time (k = domain size) Previous best: O*(kO(p^2log p)) [Chitnis et al. 12] Group FVS: O*(4p) time Works even when the group is exponentially large. Previous best: O*(2O(plog p)) [Cygan et al. 12]) Linear-time (= O(cp(n+m))) FPT algorithms using max flow for VC above LP, Almost 2SAT, and Unique Label Cover.
Future work Directed graph cut problems? Directed FVS, Directed Multiway Cut, Magnus talk Which VCSPs can be minimized on subdomain D D in FPT time? Any function f: {1, ,k}V can be extended to a k- submodular function f : {0,1, ,k}V [Hirai-Iwamasa 15] But f can take a negative value even when f is non-negative 27
