0/1/all CSPs, Half-Integral A-path Packing,
and Linear-Time FPT Algorithms

arXiv:1704.02700v2 [cs.DS] 7 Nov 2017

Yoichi Iwata∗
National Institute of Informatics
yiwata@nii.ac.jp

Yutaro Yamaguchi†
Osaka University
yutaro yamaguchi@ist.osaka-u.ac.jp

Yuichi Yoshida‡
National Institute of Informatics
yyoshida@nii.ac.jp

Abstract
A recent trend in the design of FPT algorithms is exploiting the half-integrality of LP
relaxations. In other words, starting with a half-integral optimal solution to an LP relaxation,
we assign integral values to variables one-by-one by branch and bound. This technique is general
and the resulting time complexity has a low dependency on the parameter. However, the time
complexity often becomes a large polynomial in the input size because we need to compute
half-integral optimal LP solutions.
In this paper, we address this issue by providing an O(km)-time algorithm for solving the
LPs arising from various FPT problems, where k is the optimal value and m is the number
of edges/constraints. Our algorithm is based on interesting connections among 0/1/all constraints, which has been studied in the field of constraints satisfaction, A-path packing, which
has been studied in the field of combinatorial optimization, and the LPs used in FPT algorithms.
With the aid of this algorithm, we obtain improved FPT algorithms for various problems, including Group Feedback Vertex Set, Subset Feedback Vertex Set, Node Multiway Cut, Node Unique Label Cover, and Non-monochromatic Cycle Transversal.
The obtained running time for each of these problems is linear in the input size and has the
current smallest dependency on the parameter. In particular, these algorithms are the first
linear-time FPT algorithms for problems including Group Feedback Vertex Set and Nonmonochromatic Cycle Transversal.

∗

Supported by JSPS KAKENHI Grant Number JP17K12643.
Supported by JSPS KAKENHI Grant Number JP16H06931 and JST ACT-I Grant Number JPMJPR16UR.
‡
Supported by JST ERATO Grant Number JPMJER1305 and JSPS KAKENHI Grant Number JP17H04676.
†

Contents
1 Introduction
1.1 FPT Algorithms using Half-Integral LP Relaxations
1.2 0/1/all Deletion and A-path Packing . . . . . . .
1.3 Related Work on Half-Integral A-path Packing . . .
1.4 Proof Sketch . . . . . . . . . . . . . . . . . . . . . .
1.5 Comparison to Babenko’s algorithm . . . . . . . . .
1.6 Organization . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

1
1
3
4
5
7
7

2 Definitions
8
2.1 Basic Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 0/1/all Deletion and Half-Integral Relaxation . . . . . . . . . . . . . . . . . . . . 8
2.3 Single-Branching Pair and Incremental-Test Oracle . . . . . . . . . . . . . . . . . . . 10
3 Half-Integral Packing and Covering
3.1 Preliminaries . . . . . . . . . . . . . . . . .
3.1.1 Basic F-Packing . . . . . . . . . . .
3.1.2 Augmenting Path/Pair . . . . . . . .
3.2 Finding Augmenting Path/Pair . . . . . . .
3.3 Constructing Half-Integral F-Cover . . . . .
3.4 Augmentation . . . . . . . . . . . . . . . . .
3.4.1 Simplification of Alternating Path .
3.4.2 Augmentation by Augmenting Path
3.4.3 Augmentation by Augmenting Pair .
4 Farthest Cover

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

11
11
11
12
15
19
21
21
23
25
31

5 Linear-Time FPT Algorithms
35
5.1 Algorithm for 0/1/all Deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Applications to Other Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
A Proof of Persistency

46

B Axiomatic Model

47

1

Introduction

1.1

FPT Algorithms using Half-Integral LP Relaxations

Parameterized complexity is the subject of studying the complexity of parameterized problems. A
parameterized problem with a parameter k is fixed parameter tractable (FPT) if we can solve the
problem in f (k)poly(n) time, where n is the input size. Various parameterized problems are known
to be FPT. See [8, 10] and references therein for a comprehensive list of FPT problems.
One of the motivations of studying parameterized complexity is to understand tractable subclasses of (NP-)hard problems; hence, the primary interest has been which parameterized problems
admit FPT algorithms. However, from a practical point of view, the running time with respect
to the input size must also be small. Indeed, linear-time FPT algorithms (i.e., FPT algorithms
whose running times are linear in the input size) are proposed for several problems including
Treewidth [4], Almost 2-SAT [18, 31], Feedback Vertex Set (FVS) [3], Subset FVS [21],
Directed FVS [22], and Node Unique Label Cover [23]. These works focused on reducing
the running time with respect to the input size, and hence dependency on the parameter is often
suboptimal. For example, Subset FVS admits an FPT algorithm running in O∗ (4k )1 time [19]
whereas the current best linear-time FPT algorithm has time complexity O(25.6k m) [21], where m
is the number of edges in the input graph.
The half-integrality of the LP relaxations has recently been used to design FPT algorithms for
a broad range of problems [9, 15, 17, 19, 20, 33]. To see the idea, let us consider a minimization
problem whose goal is to find a solution of size k, and suppose that it admits a half-integral LP
relaxation2 , that is, an LP relaxation with an optimal LP solution that only uses values in {0, 21 , 1}.
The algorithm is based on the standard branch-and-bound framework. First, we compute a halfintegral (optimal) LP solution. We can stop if all the variables have integral values or the sum of
the values in the LP solution exceeds k. Otherwise, we fix variables with values 1. We then pick
an arbitrary variable with value 21 , and branch into the case that its value is fixed to 0 and the
case that its value is fixed to 1. This approach has several big advantages. It can be applicable
to various problems just by changing the LP, and has a small time complexity with respect to
parameter k. For many problems including Almost 2-SAT [20], Node Multiway Cut [9], and
Group FVS [19], the current smallest dependency on the parameter is indeed achieved by this
approach.
A drawback of the abovementioned approach is that it is not trivial how to efficiently compute
half-integral LP solutions. Iwata, Wahlström, and Yoshida [19] viewed half-integrality as a discrete
relaxation. They showed that one can compute half-integral LP solutions for Almost 2-SAT and
(Edge) Unique Label Cover in time linear in the input size by reducing them to the s-t cut
problem. Moreover, they showed that we can compute LP solutions with an extremal condition,
which we call the farthest condition herein (see Section 2.2 for details), in the same running time.
Using farthest solutions, the LP lower bound strictly increases for each branching. Consequently,
they obtained linear-time FPT algorithms for these problems.
O∗ (·) hides a polynomial dependency on the input size. When focusing on reducing the f (k) part, the poly(n)
part is often ignored using this notation.
2
Most of the LPs used in the FPT algorithms are not natural LP relaxations of the original problems, but are LP
relaxations of rooted problems. For example, the rooted version of FVS is a problem of finding a minimum vertex
subset S, such that the graph obtained by removing S contains no cycles reachable from a prescribed vertex s. Note
that the existence of a half-integral LP relaxation to the rooted problem does not imply a 2-approximability of the
original problem.
1

1

Table 1: Summary of our FPT results. Here, d denotes the maximum domain size, Σ is the alphabet
set; m denotes the number of edges/constraints in the input; and TΓ denotes the time complexity for
performing group operations. All the algorithms are deterministic except for the O(25.6k m)-time
algorithm for Subset FVS. See Section 5.2 for the problem definitions.
Problem
Smallest f (k)
Existing linear-time FPT
Our result
∗
2k
0/1/all Deletion
O (d ) [19]
—
O(d2k km)
∗
2k
O(k|Σ|)
Node Unique Label Cover O (|Σ| ) [19]
|Σ|
m [23]
O(|Σ|2k km)
Two-fan Deletion
O∗ (9k ) [19]
—
O(4k km)
Monochromatically
—
—
O(4k km)
Orientable Deletion
Subset Pseudoforest
—
—
O(4k km)
Deletion
Node Multiway Cut
O∗ (2k ) [9]
O(4k m) [6, 18]
O(2k km)
Group FVS
O∗ (4k TΓ ) [19]
—
O(4k kmTΓ )
k
O(25.6 m) (randomized) [21]
Subset FVS
O∗ (4k ) [19]
O(4k km)
2O(k log k) m (deterministic) [21]
Non-monochromatic
—
O∗ (4k ) [33]
O(4k km)
Cycle Transversal
The s-t cut approach unfortunately does not work well for other problems such as Group FVS,
Subset FVS, Node Multiway Cut, and Node Unique Label Cover because it is essentially
applicable only to edge-deletion problems3 and because the auxiliary network size is generally not
linear in the input size (e.g., for Subset Feedback Edge Set, the size of the network becomes
2O(m) ). We need to resort to solving linear programs for these problems, and hence the resulting
FPT algorithms have large dependencies on the input size. Among these problems, linear-time
FPT algorithms have been obtained for Node Multiway Cut [6, 18], Subset FVS [21], and
Node Unique Label Cover [23] by problem-specific arguments without using LP relaxations.
However, they have larger dependencies on k (Table 1).
The main contribution of this study is the development of an algorithm that computes farthest
half-integral solutions to those LPs in time linear in the input size. Using the connection of
computing half-integral LP solutions and FPT algorithms, we obtain linear-time FPT algorithms
for various problems, which are summarized in Table 1. In particular, for Subset FVS, Node
Multiway Cut, and Node Unique Label Cover, we substantially improve the dependency
on the parameter. For the other problems including Group FVS and Non-monochromatic
Cycle Transversal, we obtain the first linear-time FPT algorithms. We note that, for every
problem in the table, the f (k) part in the running time of our algorithm matches or improves the
smallest known. All of these results are obtained by the same approach, i.e., the branch-and-bound
framework combined with the efficient computation of half-integral LPs, which demonstrates its
generality.
3
Note that edge-deletion problems are easily reducible to the corresponding vertex-deletion problems in most cases
by subdividing the edges and creating k copies of the original vertices.

2

1.2

0/1/all Deletion and A-path Packing

We consider the following problem, called 0/1/all Deletion, to establish a unified framework
and provide linear-time FPT algorithms for the abovementioned problems using half-integral LP
relaxations. Let V be a set of variables. Each variable v ∈ V has an individual domain D(v). A
function ϕ on V that maps each variable v ∈ V to a value ϕ(v) ∈ D(v) is called an assignment
for V . We consider the following two types of binary constraints on (u, v) ∈ V × V , called 0/1/all
constraints [7]4 .
1. Permutation constraint π(ϕ(u)) = ϕ(v), where π : D(u) → D(v) is a bijection.
2. Two-fan constraint (ϕ(u) = a) ∨ (ϕ(v) = b), where a ∈ D(u) and b ∈ D(v).
Let C be a set of 0/1/all constraints on V . We assume that C contains at most one constraint
for each pair of distinct variables u, v ∈ V . A constraint on (u, v) in C is denoted by Cuv . For a
subset U ⊆ V , we denote the set {Cuv ∈ C | u, v ∈ U } by C[U ].
0/1/all Deletion
Parameter: k, d
Input: A set of variables V each of which has a domain of size at most d, a set C of 0/1/all
constraints each of which is given as a table of size O(d), a partial assignment ϕA for a subset
A ⊆ V , and an integer k.
Question: Is there a pair of a set X ⊆ V of at most k variables and a partial assignment
ϕ for V \ X such that (1) ϕ(v) = ϕA (v) holds for every v ∈ A \ X and (2) ϕ satisfies all of
C[V \ X]?
The set X in the question is called a deletion set. The task of the optimization version of this
problem is to compute the size of a minimum deletion set. Various FPT problems can be expressed
as 0/1/all Deletion (by using a large d). Note that for several problems, we need exponentialsize domains, and hence a linear-time FPT algorithm for 0/1/all Deletion does not directly
imply linear-time FPT algorithms for such problems. We show that, by giving constraints not as
a table but as an oracle and by using a specialized branching strategy, we can obtain linear-time
FPT algorithms even for such problems in a unified way. See Section 5.2 for details.
The primal graph for C is a simple undirected graph G = (V, E) such that an edge uv ∈ E exists
if and only if a constraint Cuv on (u, v) exists. An important property of the 0/1/all constraints is
that, when fixing the value of a variable u ∈ V to p ∈ D(u), the set of values of v ∈ V satisfying
the constraint Cuv is either D(v) (when the constraint is a two-fan with a = p) or a singleton {q}
(when the constraint is a permutation with q = π(p) or a two-fan with a 6= p and b = q). The
latter-type implication is called a unit propagation.
When we are given a partial assignment ϕA for a subset A ⊆ V , unit propagations occur along
walks in the primal graph G starting at the vertices in A. If the unit propagations along two
different walks starting at (possibly the same) vertices in A lead to a contradiction (i.e., implicate
distinct singletons for the same variable), then at least one variable on the two walks must be
contained in the deletion set. The concatenation of such two walks is a walk between the vertices
in A (called an A-walk) that is said to be conflicting (see Section 2.2 for a formal definition).
This observation provides a lower bound on the minimum size of a deletion set as follows.
Suppose that a deletion set X ⊆ V with |X| = k exists, and let F = FC,ϕA be the set of all
4

Precisely speaking, the permutation and two-fan constraints together with empty and complete constraints are
obtained by enforcing arc-consistency on the 0/1/all constraints introduced in [7].

3

conflicting A-walks in the primal graph G for C with respect to ϕA . Then, the remaining graph
G − X cannot have a walk in F (i.e., X is a cover (or a hitting set) of F). Hence, the minimum
size of such a cover is at most k.
We now consider an LP relaxation of finding a minimum cover of the set F of all conflicting
A-walks in G, called the F-covering
a function x : V → R≥0
P problem: we are required to find P
minimizing the total
value
|x|
:=
x(v)
under
the
constraint
that
v∈V
v∈W x(v) ≥ 1 for every
P
W ∈ F, where “ v∈W ” means the summation over the occurrences of vertices v in W considering
the multiplicity (e.g., x(v) is summed twice if W intersects v twice). The dual of this LP is written
down as follows, as the F-packing
P problem: we are required
P to find a function y : F → R≥0
maximizing the total value |y| := W ∈F y(W ) subject to W ∈F : v∈W y(W ) ≤ 1 for every v ∈ V ,
where
P we also consider the multiplicity of the occurrences of vertices in a walk in the summation
“ W ∈F : v∈W ” (e.g., y(W ) is summed twice if W intersects v twice).
We then propose an O(kmT )-time algorithm for finding a pair of a half-integral F-cover x and
a half-integral F-packing y with |x| = |y| ≤ k2 (if exists, and otherwise correctly concluding it),
where m = |C| and T is the running time of a certain oracle for simulating unit propagations (see
Section 2.3 for the detail). Note that, by LP duality, these x and y are both optimal solutions to
the F-covering and F-packing problems, respectively.
Combining our algorithm with the result in [19] (see also Theorem 1 in Section 2.2), we can
obtain an FPT algorithm for 0/1/all Deletion and, hence, FPT algorithms for other various
problems. Section 5 provides the detailed discussion for each specific problem.

1.3

Related Work on Half-Integral A-path Packing

When C contains only the permutation constraints, the integral version of the F-packing problem
has been studied under the name of non-returning A-path packing [26, 28, 34]. This is the current
most general case of tractable (integral) path packing problems. Our half-integral result suggests a
conjecture that the integral packing of conflicting paths will also be tractable. We also believe that
ideas behind our half-integral algorithm will be useful for obtaining a faster algorithm for integral
path packing problems.
For a further special case (of non-returning A-path packing), called internally disjoint5 A-path
packing, the integral version of the dual covering problem coincides with Node Multiway Cut,
and its LP relaxation is used in the branch-and-bound FPT algorithm [9] and a 2-approximation
algorithm [14] for this problem.
Several previous works in the field of combinatorial optimization can be found as regards the
half-integral version of internally disjoint A-path packing. Garg et al. [14] and Pap [27, 29] found
that both LPs always enjoy half-integral optimal solutions even if each non-terminal vertex has
an individual integral capacity instead of 1. Hirai [16] and Pap [27, 29] developed algorithms
for finding such half-integral optimal solutions, which both run in strongly polynomial time (i.e.,
the number of elementary operations performed through each algorithm does not depend on the
capacity values). One makes use of a sophisticated algorithm for the submodular flow problem [13]
whereas the other relies on the ellipsoid method to solve LPs whose coefficient matrices only have
0, ±1 entries [12]. Specializing on the uncapacitated case, Babenko [1] provided an O(knm)-time
algorithm for finding a maximum half-integral packing, where n and m are the numbers of vertices
and edges, respectively, and k denotes the optimal value, which is at most O(n). Our algorithm
5

They can share terminals, but not inner vertex or edge.

4

(1) connecting distinct vertices

(2) path to an odd cycle

(3) prefix-sharing pair

Figure 1: Augmentations for half-integral matching. Thick solid lines denote edges of weight 1,
dashed lines denote edges of weight 12 , and thin solid lines denote edges of weight 0
for the F-packing/covering problems improves the previous best running time even against this
(internally disjoint) special case.

1.4

Proof Sketch

Basically, we iteratively augment a half-integral F-packing y, and construct a half-integral F-cover
x of the same size when no augmentation is possible. Since the F-covering and F-packing problems
are the dual LPs to each other, this implies that x and y are optimal solutions to these problems.
In the case of the maximum s-t flow, when we failed to find an augmenting path, we can construct
a minimum s-t cut by taking the set of edges on the flow that separates the vertices visited by
the failed search from the unvisited vertices. Similarly, we can construct a minimum half-integral
F-cover by taking the set of vertices on the half-integral F-packing that separates visited vertices
from the unvisited vertices.
We describe the idea behind our algorithm for F-packing by showing a relation to computing
half-integral (non-bipartite) matchings, which are often called 2-matchings in the field of combinatorial optimization (see [32, Chapter 30] for the basics). Although we can easily obtain a maximum
half-integral matching by a reduction to maximum bipartite matching [24], we propose a different approach herein. The idea behind this approach can be used for the half-integral F-packing.
We focus on special half-integral matchings that consist of vertex-disjoint edges of weight 1 and
odd cycles6 with each edge having weight 12 . A maximum half-integral matching with this special
structure is known to always exist [2]. In each step, we search for an alternating path (a path that
alternately uses edges of weight 0 and 1 and never uses the edges of weight 21 ) from the vertices not
used in the current matching. Augmentation can be categorized into three types (see Figure 1).
The first case is when we found an alternating path P connecting two distinct vertices not used
in the current matching. The current matching uses all the even edges in P . We can augment the
matching size by 1 by taking all the odd edges and discarding all the even edges.
The second case is when we found an alternating path P of length 2a + 1 ending at a vertex on
an odd cycle C of length 2b + 1. The current matching uses all the even edges in P with weight
1 and all the edges in C with weight 12 . Thus, the size of the current matching induced by P and
6

The number of edges in the cycle is odd.

5

C is a + b + 12 . We can easily augment this matching to an integral matching of size a + b + 1 by
alternately taking the edges in P and C.
The third case is when we found a pair of prefix-sharing alternating paths P of odd length and Q
of even length ending at the same vertex. This case corresponds to a blossom in Edmonds’ algorithm
for the maximum (integral) matching problem [11]. In Edmonds’ algorithm, the alternation is
applied to the common prefix and then the vertices on the cycles induced by P and Q are shrunk.
In our approach, we can augment the matching size by 12 by applying the alternation to the common
prefix, then by transforming the cycle induced by P and Q to an odd cycle with each edge having
weight 21 .
We use a similar approach in our algorithm for F-packing/covering. We focus on a special type
of half-integral F-packings that consist of disjoint paths in F of weight 1, called integral paths, and
wheels, which are the sums of an odd number of walks in F of weight 12 and correspond to odd
cycles for matching. See Section 3.1.1 for the precise definition. Although a maximum half-integral
packing with a similar special structure for a very special case of F-packing, internally disjoint Apath packing, is known to always exist [25], the existence of such a special solution was previously
unknown for any other cases. The correctness of our algorithm provides a constructive proof of the
existence.
In each step, we search for an alternating path from the vertices in A not used in the current
packing. As opposed to the case of computing half-integral matchings, the alternating paths may
use edges contained in wheels. However, for simplicity, we ignore such a case in the explanation
that follows. Roughly speaking, an alternating path is a sequence of paths P1 , . . . , P` , where Pi
is a path internally disjoint from any integral path and wheel for odd i and is fully contained in
an integral path for even i. In the alternation operation, we replace the integral path containing
P2 with the path obtained by concatenating P1 and the prefix of the integral path containing P2 .
We then replace the integral path containing P4 with . . . , and so on. The definition of alternating
paths is rather complicated in ensuring that each introduced path is in F. However, it essentially
plays the same role as that for the half-integral matching case.
Augmentation can be categorized into three types. Each of which corresponds to the one for the
half-integral matching case. When we find an alternating path connecting two distinct vertices in
A, we can augment the F-packing by 1 by applying the alternation. When we find an alternating
path ending at a vertex on a wheel that is the sum of 2a + 1 walks in F of weight 21 , we can
augment the F-packing by 12 by decomposing the wheel into a integral paths and introducing a
new integral path. We call these two types of alternating path as an augmenting path. When
we find a pair of prefix-sharing alternating paths P and Q ending at the same vertex (with some
additional conditions), we can augment the F-packing by 12 by applying the alternation to the
common prefix and then by introducing a new wheel. We call this type of a pair of alternating
paths as an augmenting pair.
We need to test the membership in F in constant time to achieve the linear time complexity. To
this end, we exploit an observation that the algorithm only tests membership against some special
walks.
To obtain linear-time FPT algorithms, we need to compute a farthest minimum half-integral
F-cover, which is an F-cover satisfying some extremal condition, in linear time. In the existing
work using the s-t cut approach [19], this is achieved by exploiting a structural property of all the
minimum s-t cuts [30]. We use a different approach because we do not have the corresponding
structural property for all the minimum half-integral F-covers. Naively, we can find a farthest

6

minimum half-integral F-cover by at most n computations of the minimum half-integral F-cover.
We show that we can regard the whole sequence of computations as at most 2k computations
of augmenting path/pair search by properly deciding the order of these computations using the
maximum half-integral F-packing. Thus, it runs in linear time in total.
Another obstacle for obtaining linear-time FPT algorithms is the existence of two-fan constraints. Because 2-SAT can be expressed as 0/1/all Deletion with k = 0 and d = 2, any
linear-time FPT algorithm for 0/1/all Deletion must be able to solve 2-SAT in linear time.
The standard linear-time algorithm for 2-SAT uses the strongly connected component decomposition of the implication graph, and the existing linear-time FPT algorithms for Almost 2-SAT,
a parameterized version of 2-SAT, also use the strongly connected component decomposition of
an auxiliary network [18, 19, 31]. We cannot use this approach because the size of the auxiliary
network becomes super-linear for our problems. In our algorithm, we do not use the strongly
connected component decomposition, but instead use a parallel unit-propagation, which is an alternative linear-time algorithm for 2-SAT.

1.5

Comparison to Babenko’s algorithm

Because our algorithm for the F-packing/covering problems improves the previous best running
time even against the internally-disjoint special case, we compare our algorithm with Babenko’s
algorithm to clarify the reason that we obtain such an improvement. While both the algorithms
iteratively augment a packing, the approaches are completely different. The main difference is the
existence of augmenting pairs and the algorithm for computing augmenting paths/pairs.
In our algorithm, we focus on packings with a special structure. Both the definition of alternating paths and the algorithm for searching augmenting paths/pairs strongly rely on this structure.
While the existence of a maximum half-integral packing with the special structure was already
known for internally disjoint A-path packing [25], Babenko’s algorithm does not directly exploit
the structure, but uses a much weaker structure. This is because his augmentation strategy does not
preserve the special structure because it does not consider a notion corresponding to augmenting
pairs of our algorithm.
In our algorithm, we directly compute an augmenting path/pair in O(m) time and hence we
can compute a maximum packing of size k in O(km) time. In contrast, in Babenko’s algorithm, an
auxiliary network and its s-t flow f are constructed from the current packing, then an f -augmenting
path for the standard maximum flow problem is computed. From the obtained f -augmenting path,
we can either augment the current packing or we can find a set of vertices that can be safely
contracted to some vertex in A. Because contractions occur at most O(n) time per augmentation,
the running time becomes O(knm).

1.6

Organization

We introduce the notions used throughout the paper in Section 2. Section 3 shows a fast algorithm
that computes a maximum half-integral F-packing and transforms it into a minimum half-integral
F-cover. Section 4 presents a fast algorithm for computing a farthest minimum half-integral Fcover. We provide linear-time FPT algorithms in Section 5 using this algorithm.

7

2
2.1

Definitions
Basic Notations

The multiplicity function 1S : U → Z≥0 for a multiset S on the ground set U is defined such that
1S (a) is the number of times that a ∈ U appears in S. For two multisets A and B on the same
ground set U , we denote by A \ B the multiset such that 1A\B (a) = max{1A (a) − 1B (a), 0} holds
for any element
a ∈ U . For a function f : U → R and a multiset S on the ground set U , we define
P
f (S) := a∈U 1S (a)f (a). For a value i ∈ R, we define f −1 (i) := {a ∈ U | f (a) = i}.
All the graphs in this study are undirected. However, we sometimes need to take care of the
direction of edges. For an undirected graph G = (V, E), we use the symbol Ê when we take care
of the direction of the edges, i.e., uv = vu for uv ∈ E but uv 6= vu for uv ∈ Ê. For simplicity, we
assume that the graphs are simple; if a graph contains multiple edges or self-loops, we can easily
obtain an equivalent simple graph by subdividing the edges. For vertex v ∈ V , we denote the set of
incident edges by δ(v). For a subset U ⊆ V , we denote the induced subgraph by G[U ] = (U, E[U ]).
For an undirected graph G = (V, E), we define a walk in G as an ordered list W = (v0 , . . . , v` )
of vertices such that vi−1 vi ∈ E for all i = 1, . . . , `. The integer ` is called the length of the walk.
We denote the first and last vertices of W by s(W ) = v0 and by t(W ) = v` , respectively, and we
say that W starts from s(W ) and ends at t(W ). We denote the multisets of vertices, inner vertices,
and (undirected) edges appeared in W by V (W ) = {v0 , . . . , v` }, by Vin (W ) = {v1 , . . . , v`−1 } =
V (W ) \ {s(W ), t(W )}, and by E(W ) = {v0 v1 , . . . , v`−1 v` }, respectively. For an edge e = uv ∈ Ê,
we simply use the same symbol e to denote the walk (u, v). A walk W is called a (simple) path
if 1V (W ) (v) ≤ 1 for every v ∈ V . A walk W is called a closed walk if s(W ) = t(W ). A closed
walk W is called a (simple) cycle if ` ≥ 3 and 1V (W )\{s(W )} (v) ≤ 1 for every v ∈ V (which
implies 1V (W ) (s(W )) = 2). We may regard a walk W as a subgraph by ignoring the direction
and the multiplicity. We say that a walk W is internally disjoint from a subgraph G0 = (V 0 , E 0 )
if none of the inner vertices of W are in V 0 and none of the edges of W are in E 0 . For a walk
W = (v0 , . . . , v` ), we define the reversed walk as W −1 = (v` , . . . , v0 ). For a walk W1 = (v0 , . . . , v`0 )
and a walk W2 = (v`0 , . . . , v` ) (where 0 ≤ `0 ≤ `), we define the concatenation of the two walks as
W1 ◦ W2 = (v0 , . . . , v` ). The notation W1 ◦ W2 implicitly implies t(W1 ) = s(W2 ).

2.2

0/1/all Deletion and Half-Integral Relaxation

We first recall 0/1/all Deletion defined in Section 1.2. We are given a set V of variables v with
individual domains D(v), a set C of 0/1/all constraints (permutation and two-fan constraints)
that can be represented by a simple undirected graph G, called the primal graph, and a partial
assignment ϕA for a subset A ⊆ V . The task is to determine whether a deletion set X ⊆ V of at
most k variables exists, for which there exists an assignment ϕ for V \X such that (1) ϕ(v) = ϕA (v)
holds for every v ∈ A \ X, and (2) ϕ satisfies every constraint Cuv ∈ C[V \ X].
As described in Section 1.2, an important property of the 0/1/all constraints is that, when fixing
the value of a variable u ∈ V to p ∈ D(u), the set of values of v ∈ V satisfying the constraint Cuv
is either D(v) or a singleton {q}. We define Cuv (p) := all in the former case and define Cuv (p) := q
in the latter case. We extend this definition to walks in the primal graph as follows. For a walk
(s) of length zero and an element p ∈ D(s), we define C(s) (p) := p. For a walk W = W 0 ◦ e
starting from s ∈ V and an element p ∈ D(s), we define CW (p) := all when CW 0 (p) = all
and CW (p) := Ce (CW 0 (p)) when CW 0 (p) 6= all. Suppose that an assignment ϕ satisfying all the

8

constraints exists. Then, either CW (ϕ(s(W ))) = all or ϕ(t(W )) = CW (ϕ(s(W ))) holds for any
walk W in the primal graph.
Let ϕA be a partial assignment for a subset A ⊆ V . For a walk W with s(W ) ∈ A, we define
impϕA (W ) := CW (ϕA (s(W ))), which represents the set of assignments for t(W ) induced by W . A
walk W is called a ϕA -implicational walk if s(W ) ∈ A and impϕA (W ) 6= all. A ϕA -implicational
walk W is called ϕA -conflicting if t(W ) ∈ A and impϕA (W ) 6= ϕA (t(W )) hold. We omit the
prefix/subscript ϕA if it is clear from the context. We use the following lemma.
Lemma 1. For any two ϕA -implicational walks P and Q ending at the same vertex, P ◦ Q−1 is
ϕA -conflicting if and only if impϕA (P ) 6= impϕA (Q).
Proof. We prove the lemma by induction on the length of Q. When the length of Q is zero,
P ◦ Q−1 = P is conflicting if and only if imp(P ) 6= ϕA (t(P )) = imp(Q). When Q = Q0 ◦ vu, we
consider three cases.
(Case 1) If P ◦ uv is not implicational, Cuv must be a two-fan (ϕ(u) = a) ∨ (ϕ(v) = b) and
imp(P ) = a. Because Q is implicational, we have imp(Q) = a. Therefore, we have imp(P ) =
imp(Q). Because any prefix of a conflicting walk is implicational, P ◦ Q−1 is not conflicting. Thus,
the lemma holds for this case.
(Case 2) If P ◦ uv is implicational and Cuv is a permutation π(ϕ(u)) = ϕ(v), we have imp(P ◦
uv) = π(imp(P )) and imp(Q0 ) = π(imp(Q)). Therefore, imp(P ◦ uv) = imp(Q0 ) if and only if
imp(P ) = imp(Q) holds. Thus, from the induction hypothesis, the lemma holds for this case.
(Case 3) If P ◦ uv is implicational and Cuv is a two-fan (ϕ(u) = a) ∨ (ϕ(v) = b), we have
imp(P ) 6= a, imp(Q) = a, imp(P ◦ uv) = b, and imp(Q0 ) 6= b. Therefore, from the induction
hypothesis, P ◦ Q−1 is conflicting. Thus, the lemma holds for this case.
For two walks P and Q ending at the same vertex, we write P 6≡ Q if P ◦ Q−1 is conflicting
and P ≡ Q if P ◦ Q−1 is not conflicting, but both P and Q are implicational7 . The abovementioned lemma implies that (≡) is an equivalence relation. This is a key property in our algorithms.
Appendix B presents an alternative axiomatic definition of implicational/conflicting walks and
show that any path systems admitting this key property can be expressed as the set of implicational/conflicting walks with 0/1/all constraints. We obtain the following corollaries from Lemma 1.
Corollary 1. If a walk W is conflicting, then W −1 is also conflicting.
Corollary 2. For three implicational walks P , Q, and R ending at the same vertex, if P ◦ Q−1 is
conflicting, then at least one of P ◦ R−1 and R ◦ Q−1 is conflicting.
We now introduce a half-integral relaxation8 of 0/1/all Deletion. Let FC,ϕA denote the set
of all ϕA -conflicting walks whose internal vertices do not intersect with A9 . When C and ϕA are
clear from the context, we simply write F to refer to FC,ϕA . Note that from Corollary 1, we can
ignore the direction of walks in F. A function x : V → {0, 21 , 1} is called a half-integral F-cover if
x(V (W )) ≥ 1 for every W ∈ F. The size of x is defined as |x| = x(V ). A function y : F → {0, 12 , 1}
7

When at least one of P or Q is not implicational, neither P ≡ Q nor P 6≡ Q holds.
Originally we should define this as an LP relaxation, but we discuss it by assuming its half integrality, which is
proved via our algorithm and LP duality.
9
This constraint is only for simplicity. From Corollary 2, if P ◦ Q−1 is conflicting for some walks P and Q ending
in A, at least one of P and Q is conflicting. Therefore, a maximum packing of conflicting walks that uses none of
such walks always exists.
8

9

P
is called a half-integral F-packing if for every vertex v ∈ V , it holds that W ∈F 1V (W ) (v)y(W ) ≤ 1.
The size of y is defined as |y| = y(F). From the LP-duality, we have |x| ≥ |y| for any pair of halfintegral F-cover x and half-integral F-packing y. Any deletion set X for 0/1/all Deletion must
intersect every ϕA -conflicting walk; hence 1X is an integral F-cover10 . Therefore, the size of the
minimum half-integral F-cover provides a lower bound on the size of the minimum deletion set.
For a half-integral F-cover x, let R(x) denote the set of vertices t such that an implicational walk
W with x(V (W )) = 0 ending at t exists.
We can prove the following property called persistency by a careful consideration of the results
in [19] (see Appendix A for a detailed discussion).
Theorem 1. Let C be a set of 0/1/all constraints on a variable set V and ϕA be a partial assignment
for a subset A ⊆ V . For any minimum half-integral FC,ϕA -cover x, there exists a minimum deletion
set X containing every vertex u with x(u) = 1 but avoiding every vertex in R(x).
We say that a minimum half-integral F-cover x0 dominates a minimum half-integral F-cover
x if R(x) ( R(x0 ) holds. A minimum half-integral F-cover x is called farthest if there exists no
minimum half-integral F-cover dominating x. Suppose that we have an O(T )-time algorithm for
computing a farthest minimum half-integral F-cover. From Theorem 1, it is not difficult to obtain
an O(d2k T )-time FPT algorithm for 0/1/all Deletion. Moreover, the base d of the exponent
can be improved to a constant for several special cases. We give a detailed discussion in Section 5.1.

2.3

Single-Branching Pair and Incremental-Test Oracle

As shown in Section 5.2, various important NP-hard problems can be expressed as a special case of
0/1/all Deletion. However, the domain size d is often ω(1) (or even exp(m) for several cases,
where m is the number of edges/constraints). Hence, if every constraint is given as the table of
size d, the total size of these tables already becomes super-linear. For obtaining linear-time FPT
algorithms, we use oracles instead of the explicit expression of the constraints to efficiently check
whether a given walk is implicational/conflicting or not.
A pair (P, Q) of implicational walks ending at the same vertex is called single-branching if either
P ◦ Q−1 forms a simple path or they can be written as P = R ◦ P 0 and Q = R ◦ Q0 for a (possibly
zero-length) path R and two walks P 0 and Q0 for which P 0 ◦ Q0−1 forms a simple cycle that is
internally disjoint from R. In our algorithm, we need to test whether a given walk is implicational
and whether P ◦ Q−1 is conflicting for a given single-branching pair (P, Q). To efficiently answer
these queries, we use a tuple (U, I, A, T ), called an incremental-test oracle, of a set U and functions
I, A, and T satisfying the following.
• Init I : A → U .
• Append A : U × Ê → U ∪ {all}. Let A∗ be a function such that
(
(
I(s) (s ∈ A)
A(A∗ (W ), e) (A∗ (W ) 6= all)
∗
∗
A ((s)) =
and A (W ◦ e) =
.
all
(s 6∈ A)
all
(A∗ (W ) = all)
Then, for any walk W , A∗ (W ) 6= all if and only if W is implicational.
10
Note that the converse may not hold. For example, we have F = ∅ when A = ∅. Therefore, X = ∅ is the
minimum integral F-cover. In contrast, X = ∅ may not be a deletion set. Thus, the half-integral relaxation does not
always lead to a 2-approximation algorithm.

10

• Test T : U × U → {true, false}. For any single-branching pair (P, Q), T (A∗ (P ), A∗ (Q)) =
true if and only if P ◦ Q−1 is conflicting.
The running time of the incremental-test oracle is defined as the maximum running time of
the three
S functions. In general, we can naively implement the incremental-test oracle by setting
U := u∈V D(u), I(s) := ϕA (s), A(x, e) = Ce (x), and T (x, y) := true iff x 6= y. We can obtain
a constant-time oracle by this naive implementation for several cases including Node Multiway
Cut. Meanwhile, the naive implementation takes O(m) time for several other cases including
Subset Feedback Vertex Set. We will see in Section 5.2 that we can implement a constanttime oracle for these cases by exploiting the constraint that the inputs to the test function are
restrited to single-branching pairs.

3

Half-Integral Packing and Covering

We prove the following theorem in this section.
Theorem 2. Let C be a set of 0/1/all constraints on variables V and ϕA be a partial assignment
for a subset A ⊆ V . Given the primal graph of C, the set A, an incremental-test oracle for (C, ϕA ),
and an integer k, we can compute a pair of minimum half-integral FC,ϕA -cover x and maximum
half-integral FC,ϕA -packing y with |x| = |y| ≤ k2 or correctly conclude that the size of the minimum
half-integral FC,ϕA -cover is at least k+1
2 in O(kmT ) time, where m is the number of constraints
and T is the running time of the incremental-test oracle.
Our algorithm is based on a simple augmentation strategy summarized as follows. Starting
with y(W ) = 0 for every W ∈ F, we repeatedly update a half-integral F-packing y that always
consists of only two types of conflicting walks defined in Section 3.1.1. We search an augmenting
path/pair (see Section 3.1.2) in each iteration using Algorithm 1 described in Section 3.2. If one is
found, we can improve the current F-packing y in linear time by Lemmas 2 and 3 (Augmentation);
otherwise, as shown in Section 3.3, we can naturally construct a half-integral F-cover of size |y|,
which guarantees the optimality of y with the aid of the LP-duality. Since each augmentation
increases |y| by at least 21 , the number of iterations is bounded by k + 1. Algorithm 1 can be
implemented in linear time by Lemma 6, which concludes Theorem 2.

3.1
3.1.1

Preliminaries
Basic F-Packing

In what follows, we focus on F-packings that consist of only two types of conflicting walks. One is
a simple path I ∈ F of weight 1, which is called an integral path. The other is a wheel defined as
follows and consists of an odd number of conflicting walks of weight 21 .
Definition 1. A pair of a simple cycle C = H1 ◦ . . . ◦ Hd of weight 21 and (possibly zero-length)
paths {S1 , . . . , Sd } of weight 1 is called a wheel if it satisfies the following conditions (Figure 2).
1. d is an odd positive integer.
2. For any i, Si is a path from A to s(Hi ) = t(Hi−1 ) (where H0 = Hd ) that is internally disjoint
from C.
11

𝐻5
𝑆5

𝐻1

𝑆2

𝐴
𝐻4

Spoke

𝑆1

𝐻2

𝑆4

𝑆3
𝐻3

Half-integral cycle

Figure 2: Wheel of degree 5.
3. For any distinct i and j, Si and Sj share no vertices.
−1
4. For any i, Si ◦ Hi ◦ Si+1
∈ F, where Sd+1 = S1 .

The integer d is called the degree of the wheel, the cycle C is called the half-integral cycle of the
wheel, and the paths {S1 , . . . , Sd } are called the spokes of the wheel.
Note that a wheel of degree 1 is a closed walk S1 ◦ C ◦ S1−1 ∈ F of weight 21 , and a wheel of
degree d ≥ 3 is a sum of d simple paths {S1 ◦ H1 ◦ S2−1 , . . . , Sd ◦ Hd ◦ S1−1 } ⊆ F of weight 21 .
A half-integral F-packing y is called a basic F-packing if it is a sum of integral paths and
wheels such that each vertex is contained in at most one of the integral paths and the wheels. In
our algorithm, a basic F-packing y is dealt with as a weighted graph11 so that we can efficiently
update integral paths and wheels in y. We denote by V (y) and E(y) the sets of vertices and
(undirected) edges, respectively, that are contained in some integral path or wheel in y (i.e., of
positive weights), and particularly by V1 (y) and E1 (y), the sets of those contained in some integral
path or spoke in y (i.e., are of weight 1). A walk is called internally disjoint from y if it is internally
disjoint from the subgraph (V (y), E(y)).
For a basic F-packing y, we define two functions Fy (Forward) and By (Backward) as follows
(Figure 3). Let P be a positive-length path contained in an integral path I in y. From Corollary 1,
we can assume that I has the same direction as P . We then define paths Fy (P ) and By (P ) such
that I = Fy (P ) ◦ P ◦ By (P )−1 holds. For a vertex v contained in a spoke S in y, we denote
by Fy (v) the path from t(S) to v along S and by By (v) the path from s(S) to v along S (i.e.,
Fy (v) ◦ By (v)−1 = S −1 ). For a path P contained in a spoke S in y in the opposite direction to S,
we define Fy (P ) := Fy (s(P )) and By (P ) := By (t(P )) (i.e., Fy (P ) ◦ P ◦ By (P )−1 = S −1 ). We omit
the subscript y if it is clear from the context.
3.1.2

Augmenting Path/Pair

We first define an alternating path to define our augmenting path/pair.
Definition 2. For a basic F-packing y, a concatenation of paths P = P1 ◦ · · · ◦ Pp is called a
y-alternating path if it satisfies all the following conditions.
11

The weight is naturally defined for each vertex v and edge e by
respectively.

12

P

W ∈F

1V (W ) (v)y(W ) and

P

W ∈F

1E(W ) (e)y(W ),

𝐹(𝑣)

𝐹(𝑃)

𝐼

𝑃

𝑆

𝐹(𝑃)

𝑣

𝑆

𝐵(𝑣)

𝐵(𝑃)

𝑃 is contained in an integral path 𝐼

𝑣 is contained in a spoke 𝑆

𝑃
𝐵(𝑃)

𝑃 is contained in a spoke 𝑆

Figure 3: Definition of Fy and By .
1. The edges in E(P ) are distinct (i.e., 1E(P ) (e) ≤ 1 for every e ∈ E).
2. Every vertex in P that is not contained in any integral path or spoke in y appears in P at
most once12 (i.e., 1V (P ) (v) ≤ 1 for every v ∈ V \ V1 (y)).
3. s(P ) ∈ A \ V (y).
4. Each Pi is a path of positive length satisfying the following conditions.
(a) For any odd i, Pi is internally disjoint from y, and no internal vertex of Pi is in A.
(b) For any even i, Pi is contained in an integral path or a spoke in y. In the latter case, Pi
has the opposite direction to the spoke.
5. Let us define B(P0 ) := (s(P )). The following conditions are satisfied for any i13 (see Figure 4).
(a) If i is odd, B(Pi−1 ) ◦ Pi is implicational.
(b) If i is even and Pi is contained in an integral path, then B(Pi−2 )◦Pi−1 6≡ F (Pi ), and none
of the Pj ’s are contained in B(Pi ) for j > i. Moreover, if B(Pi−2 ) ◦ Pi−1 6≡ B(Pi ) ◦ Pi−1 ,
none of the Pj ’s are contained in F (Pi ) for j > i.
(c) If i is even and Pi is contained in a spoke, then B(Pi−2 ) ◦ Pi−1 ≡ B(Pi ) ◦ Pi−1 , and none
of the Pj ’s are contained in B(Pi ) for j > i.
Each Pi is called a segment of P . If P consists of only a single segment, it is called single-segment.
A zero-length path P = (s) with s ∈ A \ V (y) is considered as a y-alternating path with zero
segments.
We define Ty (P ) (Tail) for a y-alternating path P = P1 ◦ · · · ◦ Pp as follows: Ty (P ) := By (Pp−1 ) ◦
Pp if p is odd, and Ty (P ) := By (Pp ) if p is even. Note that Ty (P ) is always implicational. We omit
the subscript y if it is clear from the context.
Definition 3. A y-alternating path P = P1 ◦ . . . ◦ Pp is called a y-augmenting path if p is odd and
one of the following conditions is satisfied.
12

From the other properties of the y-alternating paths, a vertex contained in an integral path or a spoke can appear
twice in P . Hence, P may not be a path in the precise sense.
13
Technically, the conditions “none of the Pj ’s are contained in . . . ” mean that P does not admit a shortcut (e.g., if
there is some Pj with j > i contained in B(Pi ), we can obtain another y-alternating path P1 ◦· · ·◦Pi−1 ◦W ◦Pj+1 ◦· · · Pp ,
where W is the path from s(Pi ) to t(Pj ) along the integral path or spoke). As in the case of matroid intersection, we
need a shortcut-less alternating path.

13

𝐵(𝑃𝑖−2 )

≢

𝑃𝑖−2

𝑃𝑖−1

𝐹(𝑃𝑖−2 )

𝐹(𝑃𝑖 )
𝑃𝑖

𝐵(𝑃𝑖−2 )

≡

𝑃𝑖−2

𝑃𝑖−1

𝐹(𝑃𝑖−2 )

𝐵(𝑃𝑖 )

𝑃𝑖 is contained in an integral path

𝐹(𝑃𝑖 )
𝑃𝑖
𝐵(𝑃𝑖 )

𝑃𝑖 is contained in a spoke

Figure 4: Conditions for alternating paths.
1. t(P ) ∈ A \ V (y), and T (P ) is conflicting.
2. t(P ) is contained in a half-integral cycle, but in no spokes (i.e., t(P ) ∈ V (y) \ V1 (y)).
3. t(P ) is contained in a spoke S, and the following two conditions are satisfied.
(a) T (P ) 6≡ B(t(P )).
(b) For any Pj contained in the spoke S, t(P ) is contained in F (Pj ).
Definition 4. Let P = P1 ◦ · · · ◦ Pp and Q = Q1 ◦ · · · ◦ Qq be a pair of y-alternating paths ending
at the same vertex. (P, Q) is called a y-augmenting pair if it satisfies all the following conditions.
1. P and Q can be written as P = R ◦ P 0 and Q = R ◦ Q0 , respectively, for some walk R such
that P 0 and Q0 share no edges.
2. T (P ) 6≡ T (Q).
3. At least one of p and q is odd, and if both of p and q are odd, t(P ) 6∈ V (y).
4. For any Pi contained in an integral path, none of the Qj ’s are contained in B(Pi ) in the
opposite direction. Moreover, none of the Qj ’s are contained in F (Pi ) in the same direction
if B(Pi−2 ) ◦ Pi−1 6≡ B(Pi ) ◦ Pi−1 . The symmetric condition holds for any Qi contained in an
integral path.
Note that for any y-alternating path P , the condition 4 is always satisfied against (P, P ).
Therefore, in testing the condition 4 against (P, Q), we only need to test pairs (Pi , Qj ) such that
at least one of Pi or Qj is not contained in the common prefix R.
Using a y-augmenting path/pair, we can improve a basic F-packing y in linear time by the
following lemmas, whose proofs are given in Section 3.4.
Lemma 2. Given a basic F-packing y and a y-augmenting path, a basic F-packing of size at least
|y| + 21 can be constructed in linear time.
Lemma 3. Given a basic F-packing y and a y-augmenting pair, a basic F-packing of size |y| +
can be constructed in linear time.

1
2

Figure 5 illustrates an example of augmentations. We use the following example which corresponds to the internally-disjoint A0 -paths with A0 = {a, b, c, d}. Every vertex u has the same
domain D(u) = {a, b, c, d} and each edge uv has an equality (identity permutation) constraint
14

𝑐

𝑎

𝑑

𝑐

𝑑

𝑐

𝑎

1

𝑎

6

𝑑

5

4
3

2
𝑏

𝐴

𝑏

𝑎

𝑏

𝑐

𝑑

𝑏

𝐴

𝑎

4

7

2
𝑏

𝑏

𝑎

𝑏

𝑎

𝑏

𝑐

𝑑

6
2

𝐴

𝑎

1
𝑏

𝑐

𝑑

𝑏

𝑎

𝑏

𝐴

𝑏

3

𝑎

𝑏

𝐴

5

1

3

𝑏

𝑎

𝑏

𝑏

𝐴

𝑏

𝑎

𝑏

Figure 5: Example of augmentations. Thick solid lines denote edges of weight 1, dashed lines
denote edges of weight 12 , and thin solid lines denote edges of weight 0. Blue or green arrows denote
segments of augmenting paths/pairs. A number i beside an arrow means that it is the i-th segment.
ϕ(u) = ϕ(v). An alphabet beside a vertex u ∈ A shows the value ϕA (u). Any walks starting from
A is implicational, and a walk W is conflicting if and only if ϕA (s(W )) 6= ϕA (t(W )). Roughly
speaking, for an augmenting path P connecting two distinct vertices in A (i.e., when it satisfies the
condition 1 of Definition 3), we take the symmetric difference of E(y) and E(P ) (Figure 5, left).
For an augmenting path P ending at a vertex on a wheel (i.e., when it satisfies the condition 2
or 3 of Definition 3), we take the symmetric difference and then decompose the wheel into integral
paths (Figure 5, middle). For an augmenting pair (R ◦ P 0 , R ◦ Q0 ) with a common prefix R, we take
the symmetric difference of E(y) and E(R), and then introduce a new wheel whose half-integral
cycle is P 0 ◦ Q0−1 (Figure 5, right). In addition to this basic augmentation strategy, we need several
operations in ensuring that the obtained packing is a basic F-packing. See the proofs in Section 3.4
for more detail.

3.2

Finding Augmenting Path/Pair

In this subsection, we propose an algorithm for computing a y-augmenting path or pair. Algorithm 1 describes a rough sketch of the algorithm. We will describe later the details of an efficient
implementation using the incremental-test oracle. Note that in this subsection, we prove only
the soundness of the algorithm (i.e., the algorithm never returns a path or pair which is not yaugmenting). The completeness of the algorithm (i.e., the algorithm always finds a y-augmenting
path or pair if exists) follows from Lemma 7 proved in the next subsection.

15

Algorithm 1 Algorithm for computing a y-augmenting path/pair
1: Initialize a(I) ← 0 and b(I) ← ` for each integral path I of length `.
2: Initialize a(S) ← 0 for each spoke S.
3: for s ∈ A \ V (y) do
4:
P (s) ← (s) and X ← {s}.
5:
while X 6= ∅ do
6:
Pick a vertex u ∈ X and remove u from X.
7:
for e = uv ∈ δ(u) \ E(y) such that T (P (u)) ◦ e is implicational do
8:
if v is visited then
9:
if T (P (u)) ◦ e 6≡ T (P (v)) then return (P (u) ◦ e, P (v))
10:
else if v is contained in an integral path I = (v0 , . . . , v` ) then
11:
Let i be the index such that vi = v.
12:
if T (P (u)) ◦ e 6≡ (v` , . . . , vi ) then
13:
for j ∈ {a(I), . . . , i − 1} do
14:
P (vj ) ← (P (u) ◦ e) ◦ (vi , . . . , vj ) and X ← X ∪ {vj }.
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:

a(I) ← i.
if T (P (u)) ◦ e 6≡ (v0 , . . . , vi ) then
for j ∈ {i + 1, . . . , b(I)} do
P (vj ) ← (P (u) ◦ e) ◦ (vi , . . . , vj ) and X ← X ∪ {vj }.
b(I) ← i.
else if v is contained in a spoke S = (v0 , . . . , v` ) then
Let i be the index such that vi = v.
if T (P (u)) ◦ e 6≡ (v0 , . . . , vi ) then return P (u) ◦ e
for j ∈ {a(S), . . . , i − 1} do
P (vj ) ← (P (u) ◦ e) ◦ (vi , . . . , vj ) and X ← X ∪ {vj }.
a(S) ← i.
else if v is contained in a half-integral cycle then
return P (u) ◦ e
else if v ∈ A then
if T (P (u)) ◦ e 6≡ (v) then return P (u) ◦ e
else (v 6∈ A ∪ V (y))
P (v) ← P (u) ◦ e and X ← X ∪ {v}.
return NO

Lemma 4. Any path returned by Algorithm 1 is a y-augmenting path, and any pair returned by
the algorithm is a y-augmenting pair.
In the algorithm, we hold two indices a(I) and b(I) for each integral path I initialized as a(I) = 0
and b(I) = `, respectively, where ` is the length of I; an index a(S) for each spoke S initialized
as a(S) = 0; a set of active vertices X initialized as X = ∅; and a y-alternating path P (v) for
each visited vertex v, where we call a vertex v visited if v has been ever pushed into X. We define
boundaries as the set of vertices consisting of va(I) and vb(I) for each integral path I = (v0 , . . . , v` )
and va(S) for each spoke S = (v0 , . . . , v` ). We preserve the following invariants during the execution
16

of the algorithm.
Lemma 5. The following invariants hold at any iteration of Algorithm 1.
1. For any visited v, the following holds:
(a) P (v) is a y-alternating path,
(b) V (P (v)) contains only visited vertices or boundaries, and
(c) P (v) has an odd number of segments if and only if v 6∈ A ∪ V (y).
2. For any visited u and v with s(P (u)) = s(P (v)), (P (u), P (v)) satisfies the condition 1 of
y-augmenting pairs (Definition 4).
3. For any integral path I = (v0 , . . . , v` ), the following holds:
(a) a(I) ≤ b(I),
(b) vi is visited if and only if i < a(I) or b(I) < i, and
(c) for any P (v) with segments P1 ◦· · ·◦Pp and any segment Pi contained in I, Pi is contained
in (va(I) , . . . , v0 ) or (vb(I) , . . . , v` ) in these directions; moreover, if B(Pi−2 ) ◦ Pi−1 6≡
B(Pi ) ◦ Pi−1 holds, then s(Pi ) = va(I) = vb(I) holds.
4. For any spoke S = (v0 , . . . , v` ), the following holds:
(a) vi is visited if and only if i < a(S), and
(b) for any P (v), all the segments of P (v) contained in S are contained in (va(S) , . . . , v0 ).
We now prove Lemma 4 and 5. All the invariants are clearly satisfied at the beginning. In
each iteration, we pick an arbitrary vertex u from X (line 6). From the invariant 1, P (u) is a
y-alternating path. We then iterate over the edges e = uv ∈ δ(u) \ E(y) such that T (P (u)) ◦ e is
implicational.
When v is already visited and T (P (u)) ◦ e 6≡ T (P (v)) holds, we return a pair (P (u) ◦ e, P (v))
(line 9).
Claim 1. (P (v), P (u) ◦ e) returned at line 9 is a y-augmenting pair.
Proof. First, we prove e 6∈ E(P (u)), which implies that P (u) ◦ e is a y-alternating path. If e ∈
E(P (u)), e−1 is either the last edge of P (u) or the last edge of an odd segment Pi of P (u) := P1 ◦· · ·◦
Pp . In the former case, T (P (u))◦e = T (P (v))◦e−1 ◦e ≡ T (P (v)) holds, which is a contradiction. In
the latter case, from the invariant 2 against (P (u), P (v)), we have P (v) = P1 ◦ · · · ◦ Pi−1 ◦ W , where
W is the path satisfying W ◦ e−1 = Pi . Because Pi+1 and Pp are contained in the same integral
−1
path or spoke in the same direction, we have B(Pi−1 ) ◦ Pi ≡ B(Pi+1 ) ◦ Pi+1
from the condition 5
−1
of y-alternating paths. Therefore, we have T (P (u)) ◦ e = B(Pp ) ◦ e = B(Pi+1 ) ◦ Pi+1
◦e ≡
−1
−1
B(Pi−1 ) ◦ Pi ◦ e = B(Pi−1 ) ◦ W ◦ e ◦ e = T (P (v)) ◦ e ◦ e ≡ T (P (v)), which is a contradiction.
Next, we prove that (P (v), P (u)◦e) satisfies all the conditions of the y-augmenting pairs (Definition 4). Suppose that s(P (u)) 6= s(P (v)) holds. Then, the vertex v has already been popped from X
and, thus, we have P (u) = P (v) ◦ e−1 , which is a contradiction. Therefore, from the invariant 2, the
condition 1 is satisfied. The condition 2 is satisfied because T (P (v)) 6≡ T (P (u)) ◦ e = T (P (u) ◦ e).
Meanwhile, the condition 3 is satisfied because the number of segments of P (u) ◦ e is odd and
because, from the invariant 1, v ∈ V (y) implies that the number of segments of P (v) is even. The
condition 4 follows from the invariant 3.
17

When v is not visited, we consider five cases: (Case 1) v is contained in an integral path; (Case
2) v is contained in a spoke; (Case 3) v is contained in a half-integral cycle (but not in spokes);
(Case 4) v ∈ A (but not in V (y)); or (Case 5) v 6∈ A ∪ V (y). Note that e is not contained in
E(P (u)) when v is not visited. Therefore, P (u) ◦ e is a y-alternating path. In case 3, we return
P (u) ◦ e, which is a y-augmenting path satisfying the condition 2 of Definition 3. In case 4, if
T (P (u)) ◦ e 6≡ (v) holds, we return P (u) ◦ e, which is a y-augmenting path satisfying the condition 1
of Definition 3, and otherwise, we do nothing. In case 5, we set P (v) ← P (u) ◦ e and insert v into
X (line 31). Because e 6∈ E(y) holds, all the invariants are clearly preserved. Finally, we consider
the remaining two cases.
(Case 1) Let I = (v0 , . . . , v` ) be the integral path containing v and let i be the index such that
vi = v. Because v is not visited, a(I) ≤ i ≤ b(I) holds from the invariant 3. If T (P (u)) ◦ e 6≡
(v` , . . . , vi ) holds, we set P (vj ) ← (P (u) ◦ e) ◦ (vi , . . . , vj ) and insert vj into X for each index
j ∈ {a(I), . . . , i − 1}, and then update a(I) ← i (lines 12–15). Similarly, if T (P (u)) ◦ e 6≡ (v0 , . . . , vi )
holds, we set P (vj ) ← (P (u)◦e)◦(vi , . . . , vj ) and insert vj into X for each index j ∈ {i+1, . . . , b(I)},
and then update b(I) ← i (lines 16–19).
Claim 2. The lines 12–19 preserve all the invariants.
Proof. The invariants 1b, 1c, 2, 3a, 3b, and 4 are clearly preserved. Let a(I) and b(I) denote the
indices before the updates. For an index j ∈ {a(I), . . . , i − 1}, let P1 ◦ · · · ◦ Pp be the segments
of P (vj ). If B(Pp−2 ) ◦ Pp−1 6≡ B(Pp ) ◦ Pp−1 holds, we have T (P (u)) ◦ e = B(Pp−2 ) ◦ Pp−1 6≡
B(Pp ) ◦ Pp−1 = (v0 , . . . , vi ). Therefore, both a(I) and b(I) are updated to i. The same argument
applies to the case of j ∈ {i + 1, . . . , b(I)}. Thus, the invariant 3c is preserved.
Finally, we prove the invariant 1a by showing that P (vj ) is a y-alternating path for any newly
visited vj . The conditions 1–4 of y-alternating paths (Definition 2) are clearly satisfied. Consider
the case of j ∈ {a(I), . . . , i − 1}. The proof for the case of j ∈ {i + 1, . . . , b(I)} is symmetric. Let
P1 ◦ · · · ◦ Pp be the segments of P (vj ). Because B(Pp−2 ) ◦ Pp−1 = T (P (u)) ◦ e 6≡ (v` , . . . , vi ) = F (Pp )
holds, the condition 5 is satisfied for p. Let Pk be a segment with k < p contained in the same
integral path I. From the invariant 3c and because a(I) ≤ j < i ≤ b(I), Pp = (vi , . . . , vj ) is
contained in F (Pk ), and B(Pk−2 ) ◦ Pk−1 ≡ B(Pk ) ◦ Pk−1 holds. Therefore, the condition 5 is
satisfied for k.
(Case 2) Let S = (v0 , . . . , v` ) be the spoke containing v and let i be the index such that vi = v.
Because v is not visited, a(S) ≤ i holds from the invariant 4. If T (P (u)) ◦ e 6≡ (v0 , . . . , vi ) holds,
we return a path P (u) ◦ e (line 22); otherwise, we set P (vj ) ← (P (u) ◦ e) ◦ (vi , . . . , vj ) and insert vj
into X for each index j ∈ {a(S), . . . , i − 1}, and then update a(S) ← i (lines 23–25).
Claim 3. P (u) ◦ e returned at line 22 is a y-augmenting path.
Proof. Because T (P (u)) ◦ e 6≡ (v0 , . . . , vi ) = B(t(P (u) ◦ e)) holds, the condition 3a of the y-augment
paths (Definition 3) is satisfied. From the invariant 4, for any segment Pk of P (u) ◦ e contained in
the spoke S, t(P (u) ◦ e) = vi is contained in F (Pk ). Therefore, the condition 3b is satisfied.
Claim 4. Lines 23–25 preserve all the invariants.
Proof. All the invariants, except for the 1a, are clearly preserved. We prove the invariant 1a by
showing that P (vj ) is a y-alternating path for any newly visited vj . The conditions 1–4 of the
18

y-alternating paths (Definition 2) are clearly satisfied. Let P1 ◦ · · · ◦ Pp be the segments of P (vj ).
Because B(Pp−2 )◦Pp−1 = T (P (u)◦e) ≡ (v0 , . . . , vi ) = B(Pp )◦Pp−1 holds, the condition 5 is satisfied
for p. Let Pk be a segment with k < p contained in the same spoke S. From the invariant 4, Pk
must be contained in (va(S) , . . . , v0 ). Therefore, Pp is contained in F (Pk ). Thus, the condition 5 is
satisfied for k.
Implementation Detail
We exploit the incremental-test oracle as follows to achieve the linear-time complexity. For each
integral path I = (v0 , . . . , v` ) and for each index i ∈ {0, . . . , `}, we precompute A∗ ((v0 , . . . , vi )) and
A∗ ((v` , . . . , vi )). For each spoke S = (v0 , . . . , v` ) and for each index i ∈ {0, . . . , `}, we precompute
A∗ ((v0 , . . . , vi )). These precomputations can be done in O(nT ) time, where T is the running time
of the oracle.
For each visited vertex v, instead of explicitly holding P (v), we hold (1) prev(v) that represents
the edge picked at line 7 in the iteration when P (v) is assigned and (2) tail(v) := A∗ (T (P (v))).
When the algorithm finds a y-augmenting path or pair, we restore P (v) using the table of prev(v)
in O(n) time. For an edge e = uv ∈ δ(u) \ E(y), we have A∗ (T (P (u)) ◦ e) = A(tail(u), e), which
can be computed in O(T ) time. For any index j picked at line 13 or 23, we have tail(vj ) =
A∗ (T (P (vj ))) = A∗ ((v0 , . . . , vj )), which has been precomputed. For any index j picked at line 17,
we have tail(vj ) = A∗ (T (P (vj ))) = A∗ ((v` , . . . , vj )), which has been precomputed. When v 6∈
A ∪ V (y), we have tail(v) = A(tail(u), e). Thus, we can compute tail(w) in O(T ) time for each
newly visited vertex w.
Next, we show that each of the equivalence tests in the algorithm can be done in O(T ) time.
Let e = uv be the edge picked at line 7. First, we consider the equivalence test at line 9. If
prev(v) = e−1 holds, we have T (P (u)) ◦ e ≡ T (P (v)); otherwise, (T (P (u)) ◦ e, T (P (v))) forms a
single-branching pair from the invariant 2, for which we can test T (P (u)) ◦ e 6≡ T (P (v)) by asking
T (A(tail(u), e), tail(v)) in O(T ) time. Next, we consider the equivalence test at line 12. Because
(T (P (u) ◦ e), (v` , . . . , vi )) forms a single-branching pair, we can test T (P (u)) ◦ e 6≡ (v` , . . . , vi ) by
asking T (A(tail(u), e), A∗ ((v` , . . . , vi ))). This can be done in O(T ) time because A∗ ((v` , . . . , vi ))
has been precomputed. The same argument applies to the equivalence tests at lines 16 and 22.
The equivalence test at line 29 can be done in O(T ) time by asking T (A(tail(u), e), I(v)).
Now, we have shown that tail(v) can be computed in O(T ) time for each visited vertex v, and
that all the equivalence tests can be done in O(T ) time for each edge picked at line 7. Because
each vertex is pushed into X at most once and because each edge is processed at most twice (in
both directions), we obtain the following lemma.
Lemma 6. Given an O(T )-time incremental-test oracle, Algorithm 1 runs in O(mT ) time.

3.3

Constructing Half-Integral F-Cover

In this subsection, we prove that if Algorithm 1 fails to find a y-augmenting path or pair, we can
construct a half-integral F-cover of the same size as follows. Let a and b be the tables used in
Algorithm 1. First, we initialize x(v) ← 0 for all v ∈ V . For each integral path I = (v0 , . . . , v` ),
we set x(va(I) ) ← 21 and x(vb(I) ) ← 21 if a(I) 6= b(I), and set x(va(I) ) ← 1 if a(I) = b(I). We set
x(va(S) ) ← 21 for each spoke S = (v0 , . . . , v` ). From the construction, we have |x| = |y|. We show
that the function x is an F-cover.

19

Lemma 7. If Algorithm 1 fails to find a y-augmenting path or pair, the function x constructed as
above is a half-integral F-cover of size |y|.
We use the following lemma to prove this lemma.
Lemma 8. For any implicational walk Q with x(V (Q)) = 0, the vertex t(Q) is visited and
T (P (t(Q))) ≡ Q holds.
Proof. We prove the lemma by induction on the length of Q. For any vertex s ∈ A with x(s) = 0,
s is visited, and T (P (s)) = (s) holds. Therefore, the statement holds when the length of Q is zero.
Let Q = Q0 ◦ uv be an implicational walk with x(V (Q)) = 0. From the induction hypothesis, u is
visited, and T (P (u)) ≡ Q0 holds. Therefore, we have T (P (u)) ◦ uv ≡ Q0 ◦ uv = Q. If uv 6∈ E(y)
and v is contained in a half-integral cycle but in no spokes, the algorithm returns a y-augmenting
path at line 27. We consider the following four cases: (Case 1) v 6∈ V (y); (Case 2) uv 6∈ E(y) and
v is contained in an integral path; (Case 3) uv 6∈ E(y) and v is contained in a spoke; or (Case 4)
uv ∈ E(y).
(Case 1) Consider the iteration when u is picked at line 6. If v is already visited, T (P (u)) ◦ uv ≡
T (P (v)) holds because, otherwise, the algorithm returns a y-augmenting pair. Therefore, we have
T (P (v)) ≡ T (P (u)) ◦ uv ≡ Q. If v is not visited yet and v ∈ A, we have T (P (u)) ◦ uv ≡ (v).
Therefore, we have T (P (v)) = (v) ≡ T (P (u)) ◦ uv ≡ Q. If v is not visited yet and v 6∈ A, then v
becomes visited, and we have T (P (v)) = T (P (u)) ◦ uv ≡ Q.
(Case 2) Let I = (v0 , . . . , v` ) be the integral path containing v and let i be the index such that
vi = v. Consider the iteration when u is picked at line 6. Let a(I) and b(I) denote the values at the
beginning of this iteration (hence, x(va(I) ) and x(vb(I) ) might be zero). If i < a(I) holds, then v is
already visited, and T (P (v)) = (v0 , . . . , vi ) holds. If T (P (u)) ◦ uv 6≡ (v0 , . . . , vi ) additionally holds,
the algorithm returns a y-augmenting pair at line 9. Therefore, we have T (P (v)) = (v0 , . . . , vi ) ≡
T (P (u)) ◦ uv ≡ Q. The same argument applies to the case of i > b(I).
We now consider the remaining case that a(I) ≤ i ≤ b(I) holds. Because (v0 , . . . , vi ) 6≡
(v` , . . . , vi ) holds, at least one of T (P (u)) ◦ uv 6≡ (v0 , . . . , vi ) or T (P (u)) ◦ uv 6≡ (v` , . . . , vi ) holds.
If both hold, a(I) and b(I) are both set to i after this iteration. Therefore, we have x(v) = 1,
which is a contradiction. If T (P (u)) ◦ uv ≡ (v0 , . . . , vi ) holds, a(I) is set to i after this iteration. Because x(v) = 0, a(I) must be greater than i at the end of the algorithm. Therefore,
we have T (P (v)) = (v0 , . . . , vi ) ≡ T (P (u)) ◦ uv ≡ Q. The same argument applies to the case of
T (P (u)) ◦ uv ≡ (v` , . . . , vi ).
(Case 3) Let S = (v0 , . . . , v` ) be the spoke containing v and i be the index such that vi = v.
Consider the iteration when u is picked at line 6. Let a(S) denote the value at the beginning of
this iteration. If i < a(S) holds, then v is already visited, and T (P (v)) = (v0 , . . . , vi ) holds. If
T (P (u)) ◦ uv 6≡ (v0 , . . . , vi ) additionally holds, the algorithm returns a y-augmenting pair at line 9.
Therefore, we have T (P (v)) = (v0 , . . . , vi ) ≡ T (P (u)) ◦ uv ≡ Q.
We now consider the remaining case that a(I) ≤ i holds. If T (P (u)) ◦ uv 6≡ (v0 , . . . , vi ) holds,
the algorithm returns a y-augmenting path at line 22. Therefore, T (P (u)) ◦ uv ≡ (v0 , . . . , vi ) holds
and a(I) is set to i after this iteration. Because x(v) = 0, a(I) must be greater than i at the end
of the algorithm. Therefore, we have T (P (v)) = (v0 , . . . , vi ) ≡ T (P (u)) ◦ uv ≡ Q.
20

(Case 4) Note that in this case, uv must be contained in an integral path or a spoke because the
vertices contained in half-integral cycles are never visited. Let (v0 , . . . , v` ) be the integral path or the
spoke containing uv and let i and j be the indices such that vi = v and vj = u. Because u is visited,
T (P (u)) is either (v0 , . . . , vj ) or (v` , . . . , vj ), and w.l.o.g., we can assume the former case. If i = j−1,
then v is also visited, and we have T (P (v)) = (v0 , . . . , vj−1 ) ≡ (v0 , . . . , vj ) ◦ uv = T (P (u)) ◦ uv ≡ Q.
If i = j + 1 and v is not visited, then we have x(v) ≥ 21 , which is a contradiction. Therefore, v is
also visited, and we have T (P (v)) = (v0 , . . . , vj+1 ) = (v0 , . . . , vj ) ◦ uv = T (P (u)) ◦ uv ≡ Q.
Proof of Lemma 7. Suppose that there exists a conflicting walk W ∈ F with x(V (W )) < 1. Because
x(v) ∈ {0, 21 , 1} holds, x(V (W )) is either 0 or 21 . If x(V (W )) = 0, by applying Lemma 8 against
W , we have W ≡ T (P (t(W ))) = (t(W )), which is a contradiction. If x(V (W )) = 12 , let v be the
vertex with x(v) = 12 on W . By splitting W at v, we obtain two implicational walks Q1 and Q2
1
such that W = Q1 ◦ Q−1
2 and t(Q1 ) = t(Q2 ) = v. Because x(v) = 2 , v is contained in an integral
path or a spoke I = (v0 , . . . , v` ). Let i be the index such that vi = v and, w.l.o.g., we can assume
that a(I) = i. If I is an integral path, b(I) must be greater than i because, otherwise, we have
x(v) = 1.
If the length of Q1 is zero, i is either 0 or `. In the latter case, I is an integral path, and
` = i = a(I) < b(I) ≤ `, which is a contradiction. Thus, we have Q1 = (v0 ).
If Q1 has a positive length, let Q1 = R ◦ uv. By applying Lemma 8 against R, u is visited, and
Q1 = R◦uv ≡ T (P (u))◦uv holds. If uv is contained in I, u must be vi−1 because vi+1 is not visited.
Therefore, we have Q1 ≡ T (P (u)) ◦ uv = (v0 , . . . , vi−1 ) ◦ uv = (v0 , . . . , vi ). If uv is not contained in
I, consider the iteration when u is picked at line 6. We then have Q1 ≡ T (P (u)) ◦ uv ≡ (v0 , . . . , vi )
because, otherwise, b(I) is set to i, or the algorithm returns a y-augmenting path at line 22.
We now have proved that Q1 ≡ (v0 , . . . , vi ) holds. By applying the same argument to Q2 , we
have Q2 ≡ (v0 , . . . , vi ). Therefore, we have Q1 ≡ Q2 , which is a contradiction.

3.4
3.4.1

Augmentation
Simplification of Alternating Path

Before the proofs of Lemmas 2 and 3, we introduce a useful procedure to simplify an augmenting
path/pair obtained by Algorithm 1. We first define such an operation in a formal manner and
prove the validity just after the definition.
Definition 5. For a basic F-packing y and a y-alternating path P = P1 ◦ · · · ◦ Pp with p ≥ 2, the
simplification (y 0 , P 0 ) of (y, P ) is defined as follows (Figure 6).
• A function y 0 is constructed from y as follows:
– if P2 is contained in an integral path I, replace I with an integral path P1 ◦ F (P2 )−1 ;
– if P2 is contained in a spoke S, replace S with a spoke P1 ◦ F (P2 )−1 .
• A walk P 0 is defined as a concatenation (By (P2 ) ◦ P3 ) ◦ P4 ◦ P5 ◦ · · · ◦ Pp of max{p − 2, 1}
paths14 .
Lemma 9. For any basic F-packing y and any y-alternating path P = P1 ◦ · · · ◦ Pp with p ≥ 2, the
simplification (y 0 , P 0 ) of (y, P ) satisfies the following.
14

When p = 2, P 0 = By (P2 ).

21

≢

𝐹(𝑃2 )

≡

𝐹(𝑃2 )

𝑃1

𝑃2

𝑃1

𝑃2

𝑃3

𝑃3

𝐵(𝑃2 )

𝐵(𝑃2 )

𝐵 𝑃2 ∘ 𝑃3

𝐵 𝑃2 ∘ 𝑃3

𝑃2 is contained in an integral path

𝑃2 is contained in a spoke

Figure 6: Simplification of a basic F-packing and an alternating path.
1. y 0 is a basic F-packing with |y 0 | = |y|.
2. For any even i ≥ 4, the following holds.
(a) If Pi is contained in an integral path in y, it is also contained in an integral path in y 0 .
Moreover, Fy0 (Pi ) ≡ Fy (Pi ) and By0 (Pi ) ≡ By (Pi ) hold.
(b) If Pi is contained in a spoke in y, it is also contained in a spoke in y 0 in the direction
toward A. Moreover, Fy0 (Pi ) = Fy (Pi ) and By0 (Pi ) ≡ By (Pi ) hold.
3. P 0 = (By (P2 ) ◦ P3 ) ◦ P4 ◦ P5 ◦ · · · ◦ Pp is a y 0 -alternating path, where By (P2 ) ◦ P3 is the first
segment, and Pi (i ≥ 4) is the (i − 2)-th segment 15 .
Proof. First, we prove the first claim. When P2 is contained in an integral path I, from the
condition 5b of the y-alternating paths (Definition 2), P1 6≡ F (P2 ) holds (i.e., I 0 := P1 ◦ F (P2 )−1 ∈
F). Because P1 is internally disjoint from F (P2 ) and s(P1 ) 6∈ V (y), I 0 is a simple path. Thus,
we can replace I with the integral path I 0 . When P2 is contained in a spoke Si of a wheel,
from the condition 5c, P1 ≡ B(P2 ) ◦ P2−1 holds. From the definition of the wheel (Definition 1),
−1
Si−1 ◦ Hi−1 ◦ Si−1 and Si ◦ Hi ◦ Si+1
are both in F. As B(P2 ) ◦ P2−1 ◦ F (P2 )−1 = Si holds, we have
Si0 := P1 ◦ F (P2 )−1 ≡ Si . When the degree of the wheel is at least three, Si−1 ◦ Hi−1 ◦ Si0−1 and
−1
are both in F. When the degree of the wheel is one, S10 ◦ H1 ◦ S10−1 is in F. Thus,
Si0 ◦ Hi ◦ Si+1
this replacement of the spoke preserves the condition for the wheel.
Next, we prove the second claim. We can observe the following for any even i ≥ 4.
• If both of P2 and Pi are contained in the same integral path in y, from the condition 5b in
Definition 2, Pi is contained in Fy (P2 ), and P1 ≡ By (P2 ) ◦ P2−1 holds. Thus, Pi is contained
in the integral path P1 ◦ Fy (P2 )−1 in y 0 . If they have the same direction, P2 is contained in
15

When p = 2, P 0 consists of the single segment By (P2 ).

22

By (Pi ), and we can write By (Pi ) = (By (P2 ) ◦ P2−1 ) ◦ W for some subpath W . Then, it holds
that Fy0 (Pi ) = Fy (Pi ) and By0 (Pi ) = P1 ◦ W ≡ (By (P2 ) ◦ P2−1 ) ◦ W = By (Pi ). If they have the
opposite direction, P2 is contained in Fy (Pi ), and we can write Fy (Pi ) = (By (P2 ) ◦ P2−1 ) ◦ W
for some subpath W . Then, it holds that Fy0 (Pi ) = P1 ◦ W ≡ (By (P2 ) ◦ P2−1 ) ◦ W = Fy (Pi )
and By0 (Pi ) = By (Pi ).
• If both P2 and Pi are contained in the same spoke in y, from the condition 5c in Definition 2,
Pi is contained in Fy (P2 ), and P1 ≡ By (P2 ) ◦ P2−1 holds. Thus, Pi is contained in the spoke
P1 ◦ Fy (P2 )−1 in y 0 . Because both of them are directed toward A, we can write By (Pi ) =
(By (P2 ) ◦ P2−1 ) ◦ W for some subpath W . Then, it holds that Fy0 (Pi ) = Fy (Pi ) and By0 (Pi ) =
P1 ◦ W ≡ (By (P2 ) ◦ P2−1 ) ◦ W = By (Pi ).
• Otherwise, the integral path or the spoke containing Pi does not change. Thus, we have
Fy0 (Pi ) = Fy (Pi ) and By0 (Pi ) = By (Pi ).
Finally, we prove the third claim. Because By (P2 ) does not contain any Pi , the conditions 1–
4 in Definition 2 are satisfied. From the second claim and the property that A ◦ W ≡ B ◦ W
holds for any implicational walks A ◦ W and B satisfying A ≡ B, none of the three equivalence
relations appeared in the condition 5 change. As we have seen in the proof of the second claim,
E(By0 (Pi )) \ E(By (Pi )) ⊆ E(P1 ) and E(Fy0 (Pi )) \ E(Fy (Pi )) ⊆ E(P1 ) hold. Therefore, for any
i ≥ 4, none of the Pj ’s with j > i are newly contained in By0 (Pi ) or Fy0 (Pi ). Thus, the condition 5
is satisfied.
We obtain the following corollaries from Lemma 9 by repeatedly applying the simplifying operation.
Corollary 3. Given a basic F-packing y, a y-alternating path P = P1 ◦· · ·◦Pp , and an even integer
p0 ≤ p, a basic F-packing y 0 of the same size and a y 0 -alternating path P 0 satisfying the following
conditions can be constructed in linear time.
1. P 0 can be written as P 0 = (B 0 ◦Pp0 +1 )◦Pp0 +2 ◦· · ·◦Pp for some implicational path B 0 ≡ By (Pp0 ).
2. For any even i ≥ p0 + 2, the following holds.
(a) If Pi is contained in an integral path in y, it is also contained in an integral path in y 0 .
Moreover, Fy0 (Pi ) ≡ Fy (Pi ) and By0 (Pi ) ≡ By (Pi ) hold.
(b) If Pi is contained in a spoke in y, it is also contained in a spoke in y 0 in the direction
toward A. Moreover, Fy0 (Pi ) = Fy (Pi ) and By0 (Pi ) ≡ By (Pi ) hold.
Corollary 4. Given a basic F-packing y and a y-alternating path P = P1 ◦ · · · ◦ Pp , a basic Fpacking y 0 of the same size and a single-segment y 0 -alternating path P 0 satisfying P 0 ≡ Ty (P ) can
be constructed in linear time.
3.4.2

Augmentation by Augmenting Path

The subsection aims to prove Lemma 2.

23

𝐴

𝐴

𝐴

𝐴

𝑡 is contained in a half-integral cycle

𝑡 is contained in a spoke

Figure 7: Augmentation by a single-segment augmenting path.
Proof of Lemma 2. Let P = P1 ◦ · · · ◦ Pp be the given y-augmenting path and t = t(P ). If p > 1, by
Corollary 4, we obtain in linear time a basic F-packing y 0 of the same size and a single-segment y 0 alternating path P 0 such that t(P 0 ) = t and P 0 ≡ Ty (P ). We now show that P 0 is a y 0 -augmenting
path. If P satisfies the condition 1 or 2 of the y-augmenting paths (Definition 3), P 0 is a y 0 augmenting path because t(P 0 ) = t is still contained in A \ V (y 0 ) or V (y 0 ) \ V1 (y 0 ). If P satisfies the
condition 3, the spoke S that contains t in y might not exist in y 0 . However, from the condition 3b,
t is still contained in a spoke S 0 in y 0 , which may not be identical to S. By the same argument
as in the proof of the second statement of Lemma 9, we have By0 (t) ≡ By (t). Therefore, we have
Ty0 (P 0 ) = P 0 ≡ Ty (P ) 6≡ By (t) ≡ By0 (t). Thus, P 0 is a y 0 -augmenting path.
We can now concentrate on the case when p = 1 (Figure 7). If the condition 1 is satisfied, P
is a conflicting path containing no vertices in V (y). Therefore, we can obtain a basic F-packing
of size |y| + 1 by inserting the integral path P . Otherwise, let ({S1 , . . . , Sd }, H1 ◦ · · · ◦ Hd ) be the
wheel containing t. W.l.o.g., we can assume that t is contained in Hd or Sd .
If t is contained in Hd , let F be the prefix subpath of Hd to t and B be the suffix subpath of Hd
from t (i.e., F ◦ B = Hd ). We have Sd ◦ F 6≡ S1 ◦ B −1 because Sd ◦ Hd ◦ S1−1 ∈ F Thus, at least one
of Sd ◦ F ◦ P −1 and S1 ◦ B −1 ◦ P −1 is in F, and w.l.o.g., we can assume the former case. Then, we
can obtain a basic F-packing of size |y| + 21 by decomposing the wheel into (d − 1)/2 integral paths
−1
{S1 ◦ H1 ◦ S2−1 , S3 ◦ H3 ◦ S4−1 , . . . , Sd−2 ◦ Hd−2 ◦ Sd−1
} and by inserting an integral path Sd ◦ F ◦ P −1 .
If t is contained in Sd , we have P 6≡ B(t). Then, we can obtain a basic F-packing of size |y| + 12
by decomposing the wheel into (d − 1)/2 integral paths {S1 ◦ H1 ◦ S2−1 , S3 ◦ H3 ◦ S4−1 , . . . , Sd−2 ◦
−1
Hd−2 ◦ Sd−1
} and by inserting an integral path P ◦ B(t)−1 .

24

𝑄1′

𝑃1′

𝑅 𝑅

𝑃2

𝐻1

𝑃𝑑
𝐻2

𝑃𝑑−1

𝐴
𝑃𝑑−2

𝑃3
𝑃4

𝑆1

𝑆𝑑

𝑆2

𝐻3

𝑆4

𝐻𝑑−2

𝑆5

𝐻4

𝑃5

𝐻𝑑−1

𝐻5

(a)

𝑄2
𝑃1 𝑄1

𝑃3

𝑆𝑑−1

𝐴

𝑆3

𝑃2

𝐻𝑑

𝑃𝑑

𝐴
𝑃𝑑−1

𝑃4
𝑃5

𝑃6

(b)
Figure 8: Applying Lemma 10.

3.4.3

Augmentation by Augmenting Pair

This subsection aims to prove Lemma 3.
Intuitively, we want to augment y as follows. We first simplify the common prefix R of (P, Q) by
applying Corollary 3, and then obtain a new wheel whose half-integral cycle is P 0 ◦ Q0−1 . However,
it is not that easy. This approach does not work when P 0 or Q0 intersects with spokes or intersects
with the same integral path multiple times. Therefore, we augment y by gradually simplifying the
augmenting pair. First, we prove the lemma against a special case.
Lemma 10. Given a basic F-packing y and a y-augmenting pair (P = P1 ◦· · ·◦Pp , Q = Q1 ◦· · ·◦Qq )
satisfying all the following conditions, a basic F-packing of size |y| + 21 can be constructed in linear
time.
1. None of the Pi ’s are contained in the spokes.
2. None of the integral paths contain multiple Pi ’s.
3. One of the following two conditions is satisfied:
(a) p ≥ q = 1 or
(b) p ≥ q = 2, P1 = Q1 , and P2 and Q2 are contained in an integral path in the opposite
direction.
Proof. When (P, Q) satisfies the condition 3a, we further divide the case into the following two
cases: p = 1 or p ≥ 2.
If p = 1, (P, Q) is a single-branching pair such that P 6≡ Q. Therefore, we can obtain a basic
F-packing of size |y| + 12 by introducing a new wheel P ◦ Q−1 of degree one.
In p ≥ 2, let R be the common prefix and let us write P1 = R ◦ P10 and Q1 = R ◦ Q01 . We set
d := p + 1 and Pd := (t(P )) if p is even; otherwise, we set d := p. We define paths {H1 , . . . , Hd }
and {S1 , . . . , Sd } as follows (Figure 8 (a)).
• H1 := P10 .
• Hi := Pi for i ∈ {2, . . . , d − 1}.
• Hd := Pd ◦ Q0−1
1 .
25

• S1 := R.
• Si := F (Pi ) for even i ∈ {2, 4, . . . , d − 1}.
• Si := B(Pi−1 ) for odd i ∈ {3, 5, . . . , d}.
We now show that these paths form a wheel. The first condition of the wheel (Definition 1) is
trivially satisfied. As none of the integral paths in y contain multiple Pi ’s, the second and third
conditions are satisfied. We can see that the fourth condition is satisfied as follows.
• S1 ◦ H1 ◦ S2−1 = R ◦ P10 ◦ F (P2 )−1 = P1 ◦ F (P2 )−1 ∈ F.
−1
• Si ◦ Hi ◦ Si+1
= F (Pi ) ◦ Pi ◦ B(Pi )−1 ∈ F for even i ∈ {2, 4, . . . , d − 1}.
−1
• Si ◦ Hi ◦ Si+1
= B(Pi−1 ) ◦ Pi ◦ F (Pi+1 )−1 ∈ F for odd i ∈ {3, 5, . . . , d − 2}.
−1 = T (P ) ◦ T (Q)−1 ∈ F.
• Sd ◦ Hd ◦ S1−1 = B(Pd−1 ) ◦ Pd ◦ Q0−1
1 ◦R

Thus, we can obtain a basic F-packing of size |y| + 12 by removing the (d − 1)/2 integral paths
intersecting P and by inserting the wheel of degree d.
Finally, we consider the case when (P, Q) satisfies the condition 3b. Note that p must be odd
from the condition 3 of y-augmenting pairs (Definition 4). Let d := p. We define paths {H1 , . . . , Hd }
and {S1 , . . . , Sd } as follows (Figure 8 (b)).
• Hi := Pi+1 for i ∈ {1, . . . , d − 1}.
• Hd := Q−1
2 .
• S1 := P1 .
• Si := B(Pi ) for even i ∈ {2, 4, . . . , d − 1}.
• Si := F (Pi+1 ) for odd i ∈ {3, 5, . . . , d − 2}.
• Sd := B(Q2 ).
We now show that these paths form a wheel. The first condition of the wheel is trivially satisfied.
The second and third conditions are satisfied because none of the integral paths in y contain multiple
Pi ’s. We can see that the fourth condition is satisfied as follows.
• S1 ◦ H1 ◦ S2−1 = P1 ◦ P2 ◦ B(P2 )−1 = P1 ◦ (B(P2 ) ◦ P2−1 )−1 = Q1 ◦ F (Q2 )−1 ∈ F.
−1
• Si ◦ Hi ◦ Si+1
= B(Pi ) ◦ Pi+1 ◦ F (Pi+2 )−1 ∈ F for even i ∈ {2, 4, . . . , d − 3}.
−1
• Si ◦ Hi ◦ Si+1
= F (Pi+1 ) ◦ Pi+1 ◦ B(Pi+1 )−1 ∈ F for odd i ∈ {3, 5, . . . , d − 2}.

• Sd−1 ◦ Hd−1 ◦ Sd−1 = B(Pd−1 ) ◦ Pd ◦ B(Q2 )−1 = T (P ) ◦ T (Q)−1 ∈ F.
−1
−1
• Sd ◦ Hd ◦ S1−1 = B(Q2 ) ◦ Q−1
2 ◦ P1 = F (P2 ) ◦ P1 ∈ F.

Thus, we can obtain a basic F-packing of size |y| + 21 by removing the (d − 1)/2 integral paths
intersecting P and by inserting the wheel of degree d.

26

𝑃𝑏+1
𝑃𝑎−1

𝑃𝑏+1
𝑃𝑏

𝑃𝑎

𝑃𝑎−1
𝐹𝑦 (𝑃𝑏 )

𝑃𝑏−1
𝐵𝑦 (𝑃𝑎 )

𝐴
𝑃𝑎+1

𝑃𝑏−2
𝑃𝑎+2

𝑊
𝑃𝑏−1

𝐴

𝑃𝑎+1

𝐴
𝑃𝑏−2

𝑃𝑎+2

𝑦

𝑦′

𝑦ത

Figure 9: Applying Lemma 11.
Next, we provide two lemmas for weakening the assumptions in the abovementioned lemma.
Lemma 11. Given a basic F-packing y and a y-augmenting pair (P = P1 ◦· · ·◦Pp , Q = Q1 ◦· · ·◦Qq )
satisfying all the following conditions, a basic F-packing of size |y| + 12 can be constructed in linear
time.
1. None of the Pi ’s are contained in the spokes.
2’. Any two segments of P contained in the same integral path have the same direction.
3. One of the following two conditions is satisfied:
(a) p ≥ q = 1 or
(b) p ≥ q = 2, P1 = Q1 , and P2 and Q2 are contained in an integral path in the opposite
direction.
Proof. Note that the conditions 1 and 3 are the same as those in Lemma 10. Besides, if the
condition 3b is satisfied, from the condition 5b of y-alternating paths (Definition 2), the integral
path containing P2 and Q2 never contain any other segments. We call a segment of P obstructive if
it is contained in an integral path containing multiple segments of P . If there exist no obstructive
segments, the condition 2 of Lemma 10 is satisfied. Thus, we can obtain a basic F-packing of size
|y| + 12 by applying Lemma 10. We repeat the following process while obstructive segments exist.
Let Pa be the first obstructive segment and Pb (b > a) be the next segment contained in the
integral path containing Pa . From the condition 5b of the y-alternating paths (Definition 2), Pb is
contained in F (Pa ), and B(Pa−2 ) ◦ Pa−1 ≡ B(Pa ) ◦ Pa−1 holds. We construct a basic F-packing ȳ of
the same size and a ȳ-augmenting pair (P̄ , Q) such that the precondition of this lemma is satisfied
and the number of obstructive segments strictly decreases as follows (see Figure 9).
First, we construct a basic F-packing y 0 of size |y| − 1 by removing the integral path containing
Pa and Pb from y. Observe that P 0 := (By (Pa ) ◦ Pa+1 ) ◦ Pa+2 ◦ · · · ◦ Pb−1 is a y 0 -alternating path.
Then, by applying Corollary 4 against y 0 and P 0 , we obtain a basic F-packing y 00 of size |y|−1 and a
single-segment y 00 -alternating path P 00 satisfying P 00 ≡ Ty0 (P 0 ) = By0 (Pb−2 )◦Pb−1 = By (Pb−2 )◦Pb−1 .
From the condition 5b of the y-alternating path P , By (Pb−2 )◦Pb−1 6≡ Fy (Pb ) holds. From the choice
of Pb , Fy (Pb ) is internally disjoint from P 00 . Thus, we can obtain a basic F-packing ȳ of size |y|
27

by introducing a new integral path P 00 ◦ Fy (Pb ). Let W be the path from s(Pa ) to t(Pb ) along the
integral path and let P̄ := P1 ◦ · · · ◦ Pa−2 ◦ (Pa−1 ◦ W ◦ Pb+1 ) ◦ Pb+2 ◦ · · · ◦ Pp .
Finally, we prove that (P̄ , Q) is a ȳ-augmenting pair satisfying the preconditions of this lemma.
From the construction of ȳ and P̄ , the conditions 1–4 of the ȳ-alternating paths (Definition 2) are
clearly satisfied. The condition 5b is satisfied because Bȳ (Pa−2 ) ◦ (Pa−1 ◦ W ◦ Pb+1 ) ≡ By (Pa−2 ) ◦
Pa−1 ◦ W ◦ Pb+1 ≡ By (Pa ) ◦ Pa−1 ◦ W ◦ Pb+1 ≡ By (Pb ) ◦ Pb+1 holds. Thus, P̄ is a ȳ-alternating
path. Because Tȳ (P̄ ) ≡ Ty (P ) 6= Ty (Q) ≡ Tȳ (Q) holds and (P̄ , Q) satisfies the precondition 3
of the lemma, (P̄ , Q) is a ȳ-augmenting pair. Because no segments of P̄ are newly contained
in the spokes in ȳ, the condition 1 of the lemma is satisfied. From the choice of Pa , for any even
i ∈ {a+2, . . . , b−2}, By0 (Pi ) contains no segments from {P2 , . . . , Pa−2 }. Therefore, no two segments
of P̄ are newly contained in a same integral path in ȳ. Thus, the condition 2’ is satisfied. When
(P, Q) satisfies the condition 3a, (P̄ , Q) also satisfies the condition 3a. When (P, Q) satisfies the
condition 3b, (P̄ , Q) also satisfies the condition 3b because the integral path containing P2 and Q2
remains in ȳ. Thus, all the conditions in the lemma are satisfied.
We can find the pair (Pa , Pb ) by gradually increasing an index i, which is not reset during the
repetition, and by searching for Pj contained in F (Pi ) by traversing the integral path. Therefore,
each edge is traversed at most once through the whole process. Thus, the total running time is
linear in the graph size.
Lemma 12. Given a basic F-packing y and a y-augmenting pair (P = P1 ◦· · ·◦Pp , Q = Q1 ◦· · ·◦Qq ),
either of a y-augmenting path or a y-augmenting pair (P̄ , Q̄) satisfying all the following conditions
can be constructed in linear time.
1. All the segments of Q̄, except for the last one, are contained in P̄ .
−1
−1
0
2. P̄ can be written as P̄ = P ◦ Q−1
q ◦ Qq−1 ◦ · · · ◦ Qq 0 for some q .

3. The common prefix of (P̄ , Q̄) contains the common prefix of (P, Q).
−1
4. The following two conditions are satisfied for the new segments S := {Q−1
q , . . . , Qq 0 } of P̄ :

(a) no segments in S are contained in the spokes, and
(b) any two segments in S contained in the same integral path have the same direction.
Proof. Initially, the conditions 2–4 are trivially satisfied. We repeat the following process, which
preserves these conditions. The condition 1 is satisfied when q becomes one or Qq−1 gets contained
in P .
0
(Case 1) If both of p and q are odd, we update P 0 ← P1 ◦ · · · ◦ Pp−1 ◦ (Pp ◦ Q−1
q ) and Q ←
0
0
−1
Q1 ◦ · · · ◦ Qq−1 . Because Pp and Qq share no edges and because T (P ) ◦ T (Q ) = (B(Pp−1 ) ◦
−1 = (B(P
−1 = T (P ) ◦ T (Q)−1 holds, (P 0 , Q0 ) is
(Pp ◦ Q−1
p−1 ) ◦ Pp ) ◦ (B(Qq−1 ) ◦ Qq )
q )) ◦ B(Qq−1 )
a y-augmenting pair.
0
(Case 2) If p is even and q is odd, we update P 0 ← P1 ◦· · ·◦Pp−1 ◦Pp ◦Q−1
q and Q ← Q1 ◦· · ·◦Qq−1 .
−1 =
Because Pp and Qq share no edges and because T (P 0 ) ◦ T (Q0 )−1 = (B(Pp ) ◦ Q−1
q ) ◦ B(Qq−1 )
−1
−1
0
0
B(Pp ) ◦ (B(Qq−1 ) ◦ Qq ) = T (P ) ◦ T (Q) holds, (P , Q ) is a y-augmenting pair.

28

𝑃𝑘−1

𝑄𝑞−1
𝑄𝑞

𝑃𝑘−1

𝑊

𝑃𝑘

𝑃𝑘+1
𝑃𝑝

𝑃𝑘−1

𝑄𝑞−1
𝑄𝑞

𝑃𝑘−1
𝑃𝑘
𝑃𝑘+1

𝑊

𝑃𝑘+1
𝑃𝑝

𝑃𝑘−1

𝑃𝑘

𝑄𝑞−1
𝑄𝑞

𝑃𝑝

𝑃𝑘+1
𝑃𝑘

𝑃𝑘−1

𝑃𝑘

𝑃𝑘+1
𝑊
𝑃𝑝

𝑃𝑝

(Case 3)

𝑃𝑘+1
𝑃𝑘

(Case 4 (1))

𝑃𝑝

(Case 4 (2))

Figure 10: Applying Lemma 12.
(Case 3) If p is odd, q is even, and Qq is contained in a spoke, then we search for the nearest
segment of P contained in F (Qq ) by traversing the spoke. Note that none of the other segments of
Q are contained in F (Qq ) from the condition 5c of the y-alternating paths (Definition 2). Moreover,
each segment of P is fully contained in F (Qq ) or internally disjoint from F (Qq ) because Qq shares
no edges with P . Thus, each edge is traversed at most once through the entire process, and the total
running time of this part is linear in the graph size. If none of the Pi ’s are contained in F (Qq ), then
P is a y-augmenting path because t(P ) is contained in the spoke, and T (P ) 6≡ T (Q) = B(t(P ))
holds. Otherwise, let Pk be the nearest segment of P contained in F (Qq ); let W be the path
from s(Pk ) to t(P ) along the spoke; and let Q̄ := P1 ◦ · · · ◦ Pk−1 ◦ W (Figure 10 (left)). Because
T (Q̄) = B(W ) = B(Qq ) = T (Q) holds, (P, Q̄) is a y-augmenting pair. Note that this finishes the
process.
(Case 4) If p is odd, q is even, and Qq is contained in an integral path, then we search for the
nearest segment of P or Q contained in F (Qq ) by traversing the integral path. Because each edge
is traversed at most twice (in two directions) through the entire process, the total running time of
this part is linear in the graph size. Note that from the condition 5b of the y-alternating path Q
(Definition 2), F (Qq ) cannot contain a segment Qk such that Qk has the same direction as Qq or
has the opposite direction as Qq and B(Qk−2 ) ◦ Qk−1 6≡ B(Qk ) ◦ Q−1
k holds.
If the nearest segment is Pk such that Pk has the same direction as Qq or has the opposite
direction as Qq and B(Pk−2 ) ◦ Pk−1 6≡ B(Pk ) ◦ Pk−1 holds, let W be the path from s(Pk ) to
t(P ) along the integral path and Q̄ := P1 ◦ · · · ◦ Pk−1 ◦ W (see Figure 10 (right)). Because
T (Q̄) = B(W ) = B(Qq ) = T (Q) holds, (P, Q̄) is a y-augmenting pair, and we then finish the
process.
29

Otherwise (i.e., (a) no segments are contained in F (Qq ), (b) the nearest segment is Qk that has
the opposite direction as Qq and B(Qk−2 ) ◦ Qk−1 ≡ B(Qk ) ◦ Q−1
k holds, or (c) the nearest segment
is Pk that has the opposite direction as Qq and B(Pk−2 ) ◦ Pk−1 ≡ B(Pk ) ◦ Pk−1 holds), we update
0
P 0 ← P1 ◦ · · · ◦ Pp ◦ Q−1
q and Q ← Q1 ◦ · · · ◦ Qq−1 . Note that in this case, from the condition 5b
of the y-alternating paths (Definition 2) and the condition 4 of y-augmenting pairs (Definition 4),
conditions (b) and (c) hold not only against the nearest segment Qk or Pk , but also against any
segments contained in F (Qq ).
First, we prove that P 0 is a y-alternating path. The first four conditions of the y-alternating
paths (Definition 2) are clearly satisfied. The condition 5 is satisfied for i = p + 1 because B(Pp−1 ) ◦
Pp = T (P ) 6≡ T (Q) = B(Qq ) = F (Q−1
q ) holds. For checking the condition 5 against the other
Pi ’s, it suffices to show that for any segment Pi contained in the same integral path as Qq , it
holds that B(Pi−2 ) ◦ Pi−1 ≡ B(Pi ) ◦ Pi−1 , and Qq is contained in F (Pi ). Let Pi be a segment
contained in B(Qq ). From the condition 4 of the y-augmenting pairs (Definition 4), Pi has the
same direction as Qq . Thus, Qq is contained in F (Pi ). Therefore, from the condition 4 again,
B(Pi−2 ) ◦ Pi−1 ≡ B(Pi ) ◦ Pi−1 holds. Let Pi be a segment contained in F (Qq ). As we have discussed
earlier, B(Pi−2 ) ◦ Pi−1 ≡ B(Pi ) ◦ Pi−1 then holds, and Pi has the opposite direction as Qq , implying
that Qq is contained in F (Pi ).
Next, we prove that (P 0 , Q0 ) is a y-augmenting pair. Conditions 1 and 3 of the y-augmenting
pairs (Definition 4) are clearly satisfied. Because T (P 0 ) = B(Q−1
q ) = F (Qq ) 6≡ B(Qq−2 ) ◦ Qq−1 =
0
T (Q ) holds, the condition 2 is satisfied. For checking the condition 4, it suffices to show that (1)
none of the Qj ’s with j < q are contained in B(Q−1
q ) = F (Qq ) in the same direction as Qq ; (2)
−1 )−1 = F (Q ) ◦ Q , none of the Q ’s with j < q are contained in
if B(Pp−1 ) ◦ Pp 6≡ B(Q−1
)
◦
(Q
q
q
j
q
q
F (Q−1
q ) = B(Qq ) in the opposite direction as Qq ; (3) for any Qj contained in an integral path, Qq
is not contained in B(Qj ) in the same direction as Qj ; and (4) if B(Qj−2 ) ◦ Qj−1 6≡ B(Qj ) ◦ Q−1
j
holds, Qq is not contained in F (Qj ) in the opposite direction as Qj . All these conditions directly
follow from the condition 5b of the y-alternating path Q (Definition 2).
Finally, we prove that (P 0 , Q0 ) satisfies the conditions 2–4 of this lemma. Conditions 2 and 3
are clearly satisfied. From the condition 5b of the initial y-alternating path Q, B(Qq ) contains
none of the new segments S. Thus, if a segment in S is contained in the same integral path as Qq ,
it must be contained in F (Qq ). Therefore, it has the same direction as Q−1
q .
Finally, we prove Lemma 3 by combining Lemmas 11 and 12.
Proof of Lemma 3. First, we apply Lemma 12 against (Q, P ). If we obtain a y-augmenting path,
we obtain a basic F-packing of size |y| + 21 by applying Lemma 2. Otherwise, we obtain an updated
y-augmenting pair (Q̄, P̄ ) such that all the segments of P̄ , except for the last one, are contained in
the common prefix.
Next, we apply Lemma 12 against (P̄ , Q̄). We finish if we obtain a y-augmenting path; otherwise,
we obtain an updated y-augmenting pair (P̂ , Q̂). Let P̂ := P̂1 ◦· · ·◦ P̂p̂ and Q̂ := Q̂1 ◦· · ·◦ Q̂q̂ . Then,
Q̂q̂−1 is contained in P̂q̂−1 . Note that this implies that P̂i = Q̂i holds for any i ∈ {1, . . . , q̂ − 2}.
Moreover, P̂q̂−1 = Q̂q̂−1 also holds if q̂ is even. We have q̂ ≥ p̄ − 1 because the common prefix
of (P̂ , Q̂) contains the common prefix of (P̄ , Q̄) and because P̂p̄−1 is contained in the common
prefix of (P̄ , Q̄). Let us assume that q̂ = p̄ − 1 holds, and q̂ is odd. In this case, P̂q̂ is contained
in Q̂q̂ . Therefore, P̂q̂ = Q̂q̂ holds. Then, from the condition 3 of the y-augmenting pair (P̂ , Q̂)
(Definition 4), p̂ must be even, and P̂p̂ must be contained in the same integral path as P̂p̄ . However,

30

this violates the condition 5b of the y-alternating path P̂ because B(P̂p̄−2 )◦ P̂p̄−1 = T (Q̂) 6≡ T (P̂ ) =
B(P̂p̂ ) = B(P̂p̄ ) ◦ P̂p̄−1 holds. Thus, q̂ ≥ p̄ holds if q̂ is odd. We consider two cases.
If q̂ is odd or P̂q̂ and Q̂q̂ have the same direction, let r be the maximum even integer at most
q̂. We apply Corollary 3 independently against P̂ and Q̂ and obtain a basic F-packing y 0 of the
same size and y 0 -alternating paths P 0 and Q0 . Here, P̂i = Q̂i holds for any i ∈ {1, . . . , r − 1}, and
F (P̂r ) = F (Q̂r ) holds. Hence, the basic F-packing obtained by these two applications are the same.
We then, thus, use the same symbol y 0 . Because Ty0 (P 0 ) ≡ Ty (P̂ ) 6≡ Ty (Q̂) ≡ Ty0 (Q0 ) holds, (P 0 , Q0 )
is a y 0 -augmenting pair. We now show that (P 0 , Q0 ) satisfies the conditions in Lemma 11. Because
Q0 is single-segment, the third condition is satisfied. We have r + 2 = q̂ + 1 > p̄ when q̂ is odd,
and we have r + 2 = q̂ + 2 > p̄ when q̂ is even. Therefore, from the condition 4 of Lemma 12, the
first and the second conditions hold. Thus, we obtain a basic F-packing of size |y| + 12 by applying
Lemma 11 against (P 0 , Q0 ).
If q̂ is even and P̂q̂ and Q̂q̂ have the opposite direction, let r := q̂ − 2. We apply Corollary 3
against independently P̂ and Q̂ and obtain a basic F-packing y 0 of the same size and y 0 -alternating
paths P 0 and Q0 . Here, P̂i = Q̂i holds for any i ∈ {1, . . . , r}. Hence, the basic F-packings
obtained by these two applications are the same. We, thus, use the same symbol y 0 . Because
Ty0 (P 0 ) ≡ Ty (P̂ ) 6≡ Ty (Q̂) ≡ Ty0 (Q0 ) holds, (P 0 , Q0 ) is a y 0 -augmenting pair. We now show that
(P 0 , Q0 ) satisfies the conditions in Lemma 11. Because we set r := q̂ − 2, the number of segments of
Q0 is two. Because P̂q̂−1 = Q̂q̂−1 holds, the first segments of P 0 and Q0 are the same. Because P̂q̂ and
Q̂q̂ have the opposite direction, the second segments of P 0 and Q0 have the opposite direction. Thus,
the third condition is satisfied. Note that in this case, P̂q̂ and Q̂q̂ are contained in an integral path
and, from the condition 5b of the y-alternating paths (Definition 2), the integral path containing
P̂q̂ and Q̂q̂ never contain any other segments. Moreover, because r + 4 = q̂ + 2 > p̄, the first and
second conditions follow from the condition 4 of Lemma 12. Thus, we obtain a basic F-packing of
size |y| + 12 by applying Lemma 11 against (P 0 , Q0 ).

4

Farthest Cover

This section provides an algorithm for computing a farthest minimum half-integral F-cover and
proves the following theorem.
Theorem 3. Let C be a set of 0/1/all constraints on variables V and ϕA be a partial assignment
for a subset A ⊆ V . Given the primal graph of C, the set A, an incremental-test oracle for (C, ϕA ),
and an integer k, we can compute a pair of a farthest minimum half-integral FC,ϕA -cover x and
a maximum half-integral FC,ϕA -packing y with |x| = |y| ≤ k2 or correctly conclude that the size of
the minimum half-integral FC,ϕA -cover is at least k+1
2 in O(kmT ) time, where m is the number of
constraints, and T is the running time of the incremental-test oracle.
We use the following structure of a minimum half-integral F-cover.
Lemma 13. The following holds for any maximum basic F-packing y and any minimum halfintegral F-cover x.
1. x(V (I)) = 1 for any integral path I of y.
2. x(V (S)) =

1
2

for any spoke S of y.

31

Proof. For a wheel W , we denote the degree of W by d(W ) and the set of vertices contained in W by
)
and
V (W ). Note that V (W ) is not a multiset. First, we prove that x(V (W )) is always at least d(W
2
1
if the equality holds, then x(V (S)) = 2 holds for any spoke S of W . Let W be a wheel with a halfintegral cycle H1 ◦ · · · ◦ Hd and spokes {S1 , . . . , Sd }. We define H := V (W ) \ (V (S1 ) ∪ . . . ∪ V (Sd )).
We then have
x(V (W )) = x(H) +

d
X

x(V (Si ))

i=1
d

1X
1
−1
x(V (Si ◦ Hi ◦ Si+1
))
= x(H) +
2
2
i=1

≥

1
2

d
X

1

i=1

d
= .
2
If x(V (W )) = d2 holds, we have x(H) = 0 and x(V (Si )) + x(V (Si+1 )) = 1 for any i ∈ {1, . . . , d}.
Because d is odd, this implies that x(V (Si )) = 21 holds for any i ∈ {1, . . . , d}.
We now prove the lemma. Because all the integral paths and wheels do not share any vertices,
we have
X
X
|x| ≥
x(V (I)) +
x(V (W ))
I:integral path

X

≥

W :wheel

1+

I:integral path

X
W :wheel

d(W )
2

= |y|
= |x|.
Therefore, x(V (I)) = 1 and x(V (W )) =
W.

d(W )
2

must hold for any integral path I and any wheel

Fix an arbitrary maximum basic F-packing. From the above lemma, for every minimum halfintegral F-cover x, we can construct unique indices ax and bx satisfying the following.
1. For every integral path I = (v0 , . . . , v` ), x(vax (I) ) ≥ 21 , x(vbx (I) ) ≥
2. For every spoke S = (v0 , . . . , v` ), x(vax (S) ) =

1
2

1
2

and ax (I) ≤ bx (I) hold.

holds.

Therefore, we obtain the following corollary.
Corollary 5. A minimum half-integral F-cover x0 dominates a minimum half-integral F-cover x
if and only if the following conditions hold.
1. For every integral path I, ax (I) ≤ ax0 (I) ≤ bx0 (I) ≤ bx (I) holds.
2. For every spoke S, ax (S) ≤ ax0 (S) holds.
32

Algorithm 2 Algorithm for computing a farthest minimum half-integral F-cover
1: Compute a maximum basic F-packing y.
2: for each integral path I = (v0 , . . . , v` ) of y do
3:
while a(I) < b(I) do
4:
Contract (v0 , . . . , va(I)+1 ).
5:
if there exists a y-augmenting path or pair then
6:
Rewind the search and contraction of this iteration; break
7:
while a(I) < b(I) do
8:
Contract (v` , . . . , vb(I)−1 ).
9:
if there exists a y-augmenting path or pair then
10:
Rewind the search and contraction of this iteration; break
11: for each spoke S = (v0 , . . . , v` ) of y do
12:
while a(S) < ` do
13:
Contract (v0 , . . . , va(I)+1 ).
14:
if there exists a y-augmenting path or pair then
15:
Rewind the search and contraction of this iteration; break
16: return the minimum half-integral F-cover constructed from the current tables.
We use the following operation in our algorithm. Let P be an implicational walk ending at a
vertex t. First, we create a new vertex t0 and introduce a constraint ϕ(t) = ϕ(t0 ) (along with a new
edge tt0 ). We then insert t0 into A and set ϕA (t0 ) = imp(P ). We call this operation as contracting
P.
Lemma 14. Let P be an implicational walk ending at a vertex t and let F 0 be the set of conflicting
walks after contracting P . Then, any half-integral F 0 -cover x is also a half-integral F-cover, and
any half-integral F-cover x satisfying x(V (P ) \ {t}) = 0 is also a half-integral F 0 -cover.
Proof. The first claim is trivial because F ⊆ F 0 . We now prove the second claim. Suppose that x
is not a half-integral F 0 -cover. Then, there exists a walk W ∈ F 0 with x(V (W )) < 1. Because x
is a half-integral F-cover, W must contain the edge t0 t. Therefore, we can write W = t0 t ◦ Q−1 for
some implicational walk Q with imp(Q) 6= imp(P ). We then have x(V (P ◦ Q−1 )) = x(V (W )) < 1
and P ◦ Q−1 ∈ F, which contradicts the fact that x is a half-integral F-cover.
We now describe the algorithm for computing a farthest minimum half-integral F-cover (see
Algorithm 2). We iteratively apply the contraction in the algorithm. We denote the current set
of the conflicting walks by F and the original set by Forig . First, we compute a maximum basic
F-packing y using the algorithm in Section 3. We keep and reuse the tables (a, b, prev, and tail)
used in the last execution of Algorithm 1, which returned NO. We process the integral paths and the
spokes of y one by one, whose detail will be described later, by preserving the following invariants.
Lemma 15. The following invariants hold at any step of Algorithm 2.
1. y is a maximum basic F-packing.
2. Let x be the minimum half-integral F-cover constructed from the current tables as described
in Section 3.3 (i.e., ax = a and bx = b hold). Then, any minimum half-integral Forig -cover
dominating x is also a minimum half-integral F-cover dominating x.
33

3. For any processed integral path I, there exists no minimum half-integral F-cover x0 satisfying
a(I) < ax0 (I) ≤ bx0 (I) ≤ b(I) or a(I) ≤ ax0 (I) ≤ bx0 (I) < b(I).
4. For any processed spoke S, there exists no minimum half-integral F-cover x0 satisfying a(S) <
ax0 (S).
When all the integral paths and the spokes are processed, we return the minimum half-integral
F-cover x constructed from the current tables. We can easily prove the correctness of the algorithm
from these invariants.
Lemma 16. When all the integral paths and the spokes are processed, the minimum half-integral
F-cover x of G constructed from the current tables is a farthest minimum half-integral Forig -cover.
Proof. From the invariants 3 and 4 and Corollary 5, x is a farthest minimum half-integral F-cover.
Because Forig ⊆ F and from the invariant 1, x is also a minimum half-integral Forig -cover. Suppose
that there exists a minimum half-integral Forig -cover x0 dominating x. Then, from the invariant 2,
x0 is a minimum half-integral F-cover dominating x, which contradicts the fact that x is a farthest
minimum half-integral F-cover.
We now describe how to process the integral paths and spokes. For each integral path I =
(v0 , . . . , v` ), we first repeat the following while a(I) < b(I) holds (lines 3–6). Let i := a(I) + 1.
We first contract the implicational path (v0 , . . . , vi ). When using the incremental-test oracle, this
operation can be done in a constant time by setting I(vi0 ) = A∗ ((v0 , . . . , vi )), which has been
precomputed. We then search for a y-augmenting path or pair using Algorithm 1. Instead of
searching for a y-augmenting path/pair from scratch by initializing the tables, we restart the search
from line 4 of Algorithm 1 by setting s ← vi0 and reusing the current tables. If the restarted
search returns NO, we keep the tables updated by the restarted search and continue the repetition.
Because vi0 vi 6≡ (v` , . . . , vi ) holds, we have a(I) ≥ i after the search. If the restarted search finds
a y-augmenting path or pair, we rewind all the changes in this step (i.e., we restore the tables to
the state before the search and remove the edge vi0 vi inserted by the contraction), and then exit
the repetition. Note that we do not rewind the changes in the previous steps where the restarted
searches returned NO.
Claim 5. The restarted search can correctly compute a y-augmenting path or pair if exists.
Proof. We can virtually think as follows. Because the order of A \ V (y) at line 3 of Algorithm 1 is
arbitrary, we can choose completely the same order as the one used in the last failed search that
has constructed the current tables. Note that, from the invariant 3b in Lemma 5, vi was not visited
in the last execution. Therefore, the insertion of the edge vi0 vi does not affect the search at all. In
the end, the execution reaches to the final iteration of the while loop with s = vi0 , and all the tables
are completely the same as the current tables. Thus, instead of running Algorithm 1 from scratch,
we can use the restarted search.
Claim 6. Lines 3–6 preserve all the invariants.
Proof. Because we keep the changes only when the search fails, the invariant 1 is satisfied. The
invariant 2 follows from Lemma 14 against P := (v0 , . . . , vi ). The invariants 3 and 4 are trivial.
Note that the current integral path I is still under processing.

34

Claim 7. When the repetition of lines 3–6 ends, there exists no minimum half-integral F-cover x0
satisfying a(I) < ax0 (I) ≤ bx0 (I) ≤ b(I).
Proof. The repetition ends when a(I) becomes equal to b(I) or when a y-augmenting path or
pair is found. The former case is trivial. In the latter case, let F 0 be the set of the conflicting
walks after contracting (v0 , . . . , va(I)+1 ). Suppose that there exists a minimum half-integral Fcover x0 satisfying the condition in the lemma. Then, from Lemma 14, x0 is also a half-integral
F 0 -cover. In contrast, the size of the maximum half-integral F 0 -packing y 0 is strictly larger than |y|
because a y-augmenting path or pair is found. Thus, we have |y 0 | > |y| = |x0 | ≥ |y 0 |, which is a
contradiction.
After repeating lines 3–6, we repeat the following while a(I) < b(I) holds (lines 7–10). Let
i := b(I) − 1. We first contract the implicational path (v` , . . . , vi ), and then we restart the search
by setting s ← vi0 . If the restarted search fails, we continue the repetition, and if the restarted search
succeeds, we rewind all the changes in this step and exit the repetition. By the same argument as
in the case of lines 3–6, all the invariants are preserved and, when the repetition ends, there exists
no minimum half-integral F-cover x0 satisfying a(I) ≤ ax0 (I) ≤ bx0 (I) < b(I). Thus, the invariant 3
is satisfied for I when we have finished processing I.
Next, we repeat the following for each spoke S = (v0 , . . . , v` ) while a(S) < ` holds (lines 12–15).
Let i := a(S) + 1. We first contract the implicational path (v0 , . . . , vi ), and then restart the search
by setting s ← vi0 . We continue the repetition if the restarted search fails, and, otherwise, we
rewind all the changes in this step and exit the repetition. By the same argument as in the case
of integral paths, all the invariants are preserved and, when the repetition ends, there exists no
minimum half-integral F-cover x0 satisfying a(S) < ax0 (S). Thus, the invariant 4 is satisfied for S
when we have finished processing S.
Finally, we analyze the running time of Algorithm 2. The number of inserted edges is O(n),
and the number of while loops (lines 3–6, 7–10, or 12–15) is 2k. For each while loop, a series of the
restarted searches can be regarded as a single execution of Algorithm 1, which takes O(mT ) time.
Therefore, the total running time is O(kmT ). Thus, we obtain Theorem 3.

5
5.1

Linear-Time FPT Algorithms
Algorithm for 0/1/all Deletion

This section proposes an O(d2k km)-time algorithm for 0/1/all Deletion. Our algorithm is based
on the branch-and-bound algorithm in [19]. We exploit the farthest minimum half-integral F-cover
and parallel unit-propagation to obtain a linear-time FPT algorithm.
Let I = (C, ϕA ) be a pair of 0/1/all constraints C on a variable set V and a partial-assignment
ϕA on a subset A ⊆ V . We denote FC,ϕA by FI . For a variable u ∈ V \ A and an element a ∈ D(u),
we denote by I[u ← a] a pair (C, ϕA∪{u} ) such that ϕA∪{u} (u) = a. We denote by I − u a pair
(C[V \ {u}], ϕA\{u} ) for a variable u ∈ V , where ϕA\{u} is the restriction of ϕA to A \ {u}. We
call this operation deleting u. Let Nu := {v ∈ A | uv ∈ E, ϕA does not satisfy Cuv } for a variable
u ∈ A. We denote by I/u a pair (C[V \ ({u} ∪ Nu )], ϕA0 ) such that A0 = (A ∪ {v | Cuv (ϕA (u)) 6=
all}) \ ({u} ∪ Nu ) and ϕA0 (v) = Cuv (ϕA (u)) for v ∈ A0 \ A. We call this operation fixing u. We can
obtain an incremental-test oracle for I/u by setting I(v) = A(I(u), uv) for each v ∈ A0 \ A. We
can observe the following.

35

Lemma 17. The following holds for any pair I = (C, ϕA ) and u ∈ V .
1. I admits a deletion set of size k containing u if and only if I − u admits a deletion set of size
k − 1.
2. For any half-integral FI−u -cover x0 , the following function x is a half-integral FI -cover:
x(u) = 1 and x(v) = x0 (v) for v ∈ V \ {u}.
Proof. First, we prove the first claim. For a deletion set X for I containing u, X \ {u} is a deletion
set for I − u. For a deletion set X 0 for I − u, X 0 ∪ {u} is a deletion set for I.
Next, we prove the second claim. Let W be a walk in FI . We have x(V (W )) ≥ x0 (V (W )) ≥ 1
if W ∈ FI−u . Otherwise, W visits u; therefore, we have x(V (W )) ≥ x(u) = 1.
Lemma 18. The following holds for any pair I = (C, ϕA ) and u ∈ A.
1. I admits a deletion set of size k not containing u if and only if I/u admits a deletion set of
size k − |Nu |.
2. For any half-integral FI/u -cover x0 , the following function x is a half-integral FI -cover: x(u) =
0, x(v) = 1 for v ∈ Nu , and x(v) = x0 (v) for v ∈ V \ ({u} ∪ Nu ).
Proof. First, we prove the first claim. Let X be a deletion set for I not containing u. Because X
must contain all of Nu , X \ Nu is a deletion set for I/u of size |X| − |Nu |. For a deletion set X 0 for
I/u, X 0 ∪ Nu is a deletion set for I.
Next, we prove the second claim. Let W be a walk in FI . If W ∈ FI/u , we have x(V (W )) ≥
x0 (V (W )) ≥ 1. If W visits a vertex in Nu , we have x(V (W )) ≥ 1. Otherwise, we can write
W = uv ◦ W 0 . Then, we have W 0 ∈ FI/u , and thus, we have x(V (W )) ≥ x0 (V (W 0 )) ≥ 1.
For a minimum half-integral FI -cover x, we define an operation called a persistency reduction
as follows. We first delete every vertex in x−1 (1) in an arbitrary order, and then fix every vertex in
R(x) in an arbitrary order16 . Because x is a half-integral FI -cover, for any implicational walk W
with x(V (W ) \ {t(W )}) = 0 and x(t(W )) ≤ 12 , the value imp(W ) depends only on t(W ). Therefore,
the ordering does not affect the result and Nu = ∅ for every fixing. We denote the obtained pair
(C[V \ (x−1 (1) ∪ R(x))], ϕA0 ) by I/x.
Lemma 19. I admits a deletion set of size k if and only if I/x admits a deletion set of size
k − |x−1 (1)|.
Proof. From Theorem 1, there exists a minimum deletion set X for I such that x−1 (1) ⊆ X ⊆
V \ R(x). Therefore, from Lemma 17 and 18, the claim holds.
Lemma 20. For a farthest minimum half-integral FI -cover x, the restriction of x to V \ (x−1 (1) ∪
R(x)) is the unique minimum half-integral FI/x -cover.
Proof. Let x0 be the restriction of x. Then, x0 is a half-integral FI/x -cover because x0 (u) = 12
for every u ∈ A0 . Suppose that there exists a half-integral FI/x -cover z 0 with |z 0 | ≤ |x0 | and
z 0 6= x0 . From Lemmas 17 and 18, the following function z is a half-integral F-cover: z(u) = z 0 (u)
for u ∈ V \ (x−1 (1) ∪ R(x)), z(u) = 1 for u ∈ x−1 (1), z(u) = 0 for u ∈ R(x). Then, we have
|z| = |z 0 | + |x−1 (1)| ≤ |x0 | + |x−1 (1)| = |x|. Therefore, z is a minimum half-integral F-cover
dominating x, which is a contradiction.
16

We pick an arbitrary vertex u ∈ R(x) ∩ A and fix u. This changes R(x) and A, and we repeat the process until
R(x) becomes the empty set.

36

Algorithm 3 A linear-time FPT algorithm for 0/1/all Deletion
1: procedure Solve(I = (C, ϕA ), k)
2:
Compute a farthest minimum half-integral FI -cover x.
3:
if |x| > k then return false
4:
I ← I/x, k ← k − |x−1 (1)|.
5:
if V = ∅ then return true
6:
if A 6= ∅ then
7:
Pick a vertex u ∈ A.
8:
return Solve(I − u, k − 1) ∨ Solve(I/u, k − |Nu |)
9:
else
10:
Choose a branching set B.
11:
if there exists (u, a) ∈ B with FI[u←a] = ∅ then
12:
I ← I − R and goto line 5, where R is the set of the implicated variables.
13:
else
W
14:
return (u,a)∈B Solve(I[u ← a], k)

Let I = (C, ϕ∅ ) be a pair with A = ∅. A set of pairs B ⊆ {(u, a) | u ∈ V, a ∈ D(u)} is called
a branching set for I if it has the following property: any deletion set for I is a deletion set for at
least one of I[u ← a] with (u, a) ∈ B. Note that any deletion set for I[u ← a] is a deletion set for I.
The running time of our algorithm depends on the choice of branching sets. In general, we can use
the following standard choice: pick a vertex u ∈ V and set B := {(u, a) | a ∈ D(u)}. In the next
section, we choose different branching sets for problem-specific improvements.
Lemma 21. B := {(u, a) | a ∈ D(u)} for some u ∈ V is a branching set.
Proof. Let X be a deletion set for I, and let ϕ be a satisfying assignment for C[V \ X]. If u ∈ X, X
is a deletion set for every I[u ← a]. Otherwise, X is a deletion set for I[u ← a] with a = ϕ(u).
We now provide a linear-time FPT algorithm for 0/1/all Deletion (Algorithm 3). We denote
the size of the minimum half-integral FI -cover for a pair I = (C, ϕA ) by c(I). Solve(I, k) is a
procedure that returns true if and only if I admits a deletion set of size at most k. We prove the
following.
Theorem 4. Let I = (C, ϕA ) be a pair of a set C of 0/1/all constraints on a variable set V and
a partial assignment ϕA for a subset A ⊆ V . We are given the primal graph of C, the set A, an
O(T )-time incremental-test oracle for (C, ϕA ), and an integer k. Under the following assumptions,
Algorithm 3 correctly answers whether (C, ϕA ) admits a deletion set of size at most k or not in
O(max(2, b)2(k−c(I)) kmT ) time, where b is the integer in the assumption and m is the number of
constraints.
1. For any V 0 ⊆ V , we can choose a branching set for (C[V 0 ], ϕ∅ ) of size at most b.
2. For any V 0 ⊆ V and any (u, a) ∈ B for a possible branching set B for (C[V 0 ], ϕ∅ ), we have
an O(T )-time incremental-test oracle for (C[V 0 ], ϕ{u} ) with ϕ{u} (u) = a.
Note that for 0/1/all Deletion, we assume that each constraint is given as a table of size O(d).
Therefore, the naive implementation of the incremental-test oracle runs in a constant time. When
37

using the naive implementation of the incremental-test oracle, the second assumption trivially holds.
Thus, by using the standard choice of branching sets, the algorithm runs in O(d2(k−c(I)) km) =
O(d2k km) time.
First, we compute a farthest minimum half-integral FI -cover x. Because the size of x is a lower
bound on the size of the minimum deletion set, if |x| > k holds, there exists no deletion set of
size at most k. Otherwise, we have k − c(I) ≥ 0. From Lemma 19, we can apply the persistency
reduction and decrease k by |x−1 (1)|. This does not change the difference k − c(I) because c(I)
also decreases by |x−1 (1)|. We rename the reduced instance to I = (C, ϕA ) for simplicity of the
notation, and let G = (V, E) be the primal graph of C. We rename the restriction of x to V to x.
From Lemma 20, x is the unique minimum half-integral FI -cover that maps every vertex in A to
1
2 and every other vertex to 0. This part can be done in O(kmT ) time and we can construct an
incremental-test oracle for the new I from the incremental-test oracle for the old I.
If A 6= ∅, we pick a vertex u ∈ A and return Solve(I − u, k − 1) ∨ Solve(I/u, k − |Nu |).
Claim 8. I admits a deletion set of size at most k if and only if I − u admits a deletion set
of size at most k − 1 or I/u admits a deletion set of size at most k − |Nu |. Moreover, both of
k − 1 − c(I − u) < k − c(I) and k − |Nu | − c(I/u) < k − c(I) hold.
Proof. The first claim follows from Lemma 17 and 18. We now prove the second claim.
Suppose that I − u admits a half-integral FI−u -cover z 0 of size at most |x| − 1 = c(I) − 1. Then,
from Lemma 17, we can construct a half-integral FI -cover z of size at most |x| with z(u) = 1.
Therefore, z is a minimum half-integral FI -cover with x 6= z, which contradicts the uniqueness
of x.
Suppose that I/u admits a half-integral FI/u -cover z 0 of size at most |x| − |Nu | = c(I) − |Nu |.
Then, from Lemma 18, we can construct a half-integral FI -cover z of size at most |x| with z(u) = 0.
Therefore, z is a minimum half-integral FI -cover with x 6= z, which contradicts the uniqueness
of x.
If A = ∅, we choose a branching set B of size at most b. For each (u, a) ∈ B, we check
whether FI[u←a] = ∅ or not by the unit-propagation (i.e., by applying Algorithm 1 against the
empty packing). If there exists such (u, a), let R be the set of the implicated variables (i.e., R(0)
for the empty cover 0 that always returns 0). Let m0 be the number of edges incident to a vertex
in R, and suppose that (u, a) is the pair minimizing m0 . The unit-propagation for (u, a) takes only
O(m0 T ) time. Hence, by running the unit-propagation for every (u, a) ∈ B in parallel, which is
simulated in a single processor in a round-robin fashion, we can find such (u, a) in O(bm0 T ) time.
We then set I ← I − R, where I − R is the pair obtained by deleting every vertex v ∈ R, and go
back to line 5.
Claim 9. I admits a deletion set of size at most k if and only if I − R admits a deletion set of
size at most k.
Proof. Any deletion set for I is also a deletion set for I − R. Let X be a deletion set for I − R,
and let ϕV \(R∪X) be a satisfying assignment for C[V \ (R ∪ X)]. From the construction of R,
C[R] admits a satisfying assignment ϕR , and every constraint Cvw with v ∈ R and w 6∈ R is
a two-fan (ϕ(v) = a) ∨ (ϕ(w) = b) with a = ϕR (v). Therefore, an assignment ϕV \X such that
ϕV \X (v) = ϕR (v) for v ∈ R and ϕV \X (v) = ϕV \(R∪X) (v) for v ∈ V \ (R ∪ X) satisfies C[V \ X].
Thus, X is also a deletion set for I.
38

If FI[u←a] 6= ∅ for all (u, a) ∈ B, we return

W

(u,a)∈B

Solve(I[u ← a]).

Claim 10. I admits a deletion set of size at most k if and only if at least one of I[u ← a] admits
a deletion set of size k. Moreover, k − c(I[u ← a]) < k − c(I) for every (u, a) ∈ B.
Proof. The first claim follows from the definition of the branching set. Because FI[u←a] 6= ∅, we
have k − c(I[u ← a]) ≤ k − 21 < k = k − c(I).
We now have proved the correctness of the algorithm. Finally, we analyze the running time.
Let T (∆) be the running time of Solve(I, k) when ∆ := k − c(I). We can compute a farthest
minimum half-integral FI -cover in O(kmT ) time. If A 6= ∅, we branch into two cases and ∆
decreases by at least 21 for each case. Therefore, we have T (∆) ≤ 2T (∆ − 12 ) + O(kmT ). If A = ∅,
we search for (u, a) ∈ B with FI[u←a] = ∅ by the parallel unit-propagation. If there exists such
(u, a), the parallel unit-propagation takes O(bm0 T ) time, and m decreases by m0 . Therefore, in
O(bmT ) time, we reach to the state that either V = ∅ or there exists no such (u, a). In the latter
case, we branch into at most b cases, and ∆ decreases by at least 12 for each case. Therefore, we
have T (∆) ≤ bT (∆ − 21 ) + O(kmT + bmT ). Thus, we have T (∆) = O(max(2, b)2∆ kmT ).

5.2

Applications to Other Problems

Finally, we show that various NP-hard problems can be expressed as a special case of 0/1/all
Deletion. Note that we use A = ∅ for every problem other than Node Multiway Cut. We
obtain a linear-time FPT algorithm for each problem by giving an incremental-test oracle and a
specialized choice of branching sets.
Node Unique Label Cover
Parameter: k, |Σ|
Input: A finite alphabet Σ, a graph G = (V, E), a permutation πe of Σ for every edge e ∈ Ê
−1 given as a table of size |Σ|, and an integer k.
such that πuv = πvu
Question: Is there a pair of set X ⊆ V of at most k vertices and assignment ϕ : V \ X → Σ
such that πuv (ϕ(u)) = ϕ(v) for every uv ∈ E[V \ X]?
Two-fan Deletion
Parameter: k
Input: A set of variables V , a set of two-fan constraints on V of the form (ϕ(u) = a)∨(ϕ(v) =
b) given as a pair (a, b), and an integer k.
Question: Is there a pair of set X ⊆ V of at most k variables and assignment ϕ satisfying
every constraint Cuv ∈ C[V \ X]?
These two problems are special cases of 0/1/all Deletion such that the set of constraints is
limited to permutation or two-fan constraints. Note that the size of the domain is not a parameter
for Two-fan Deletion. The naive implementation of the incremental-test oracle for these problems runs in a constant time. Thus, we can solve Node Unique Label Cover in O(|Σ|2k km)
time. We can use the following choice of a branching set for Two-fan Deletion: pick a two-fan
constraint (ϕ(u) = a) ∨ (ϕ(v) = b) and set B := {(u, a), (v, b)}. Thus, we can solve Two-fan
Deletion in O(22k km) = O(4k km) time.
Lemma 22. B := {(u, a), (v, b)} for a two-fan constraint (ϕ(u) = a) ∨ (ϕ(v) = b) is a branching
set.

39

Proof. Let X be a deletion set for I and let ϕ be an assignment for V \ X satisfying C[V \ X]. If
u ∈ X, X is a deletion set for I[u ← a], and if v ∈ X, X is a deletion set for I[v ← b]. Otherwise,
at least one of ϕ(u) = a or ϕ(v) = b holds. X is a deletion set for I[u ← a] in the former case,
while X is a deletion set for I[v ← b] in the latter case.
The next two problems generalize Pseudoforest Deletion [5] in different directions, where
a pseudoforest is a graph in which the number of edges is at most the number of vertices for every
connected component.
A graph is called monochromatically orientable if there exists an edge orientation such that, for
every vertex, all the incoming edges are monochromatic. It is known that a graph is a pseudoforest
if and only if there exists an edge orientation such that, for every vertex, the number of incoming
edges is at most one. Therefore, when every edge has a distinct color, a graph is monochromatically
orientable if and only if it is a pseudoforest. Thus, the following problem is a generalization of
Pseudoforest Deletion.
Monochromatically Orientable Deletion
Parameter: k
Input: An edge-colored graph G = (V, E) and an integer k.
Question: Is there a set X ⊆ V of at most k vertices such that G − X is monochromatically
orientable?
We can solve Monochromatically Orientable Deletion in O(4k km) time by the following
reduction to Two-fan Deletion. Let L be the set of colors. For each vertex v ∈ V , we create a
variable v with domain D(v) = L, which represents the color of the incoming edges. We create a
two-fan constraint (ϕ(u) = c) ∨ (ϕ(v) = c) for each edge uv ∈ E of color c ∈ L.
Lemma 23. A graph G = (V, E) is monochromatically orientable if and only if the corresponding
set C of two-fan constraints is satisfiable.
Proof. From a monochromatic orientation of G, we can construct a satisfying assignment ϕ as
follows: we set ϕ(v) := c for each vertex v ∈ V , where c is the unique color of the incoming edges
or an arbitrary color if v has no incoming edges. From a satisfying assignment ϕ, we can construct
a monochromatic orientation by orienting each edge uv ∈ E of color c so that the edge is directed
toward u if ϕ(u) = c, and toward v otherwise.
Another generalization of Pseudoforest Deletion is presented as follows. For a graph
G = (V, E) and an edge e = uv ∈ E, contracting e is an operation deleting the edge e and merging
u and v into a new vertex e. Note that this operation may create parallel edges (edges uw and vw
become parallel edges) and self-loops. If G has parallel edges connecting u and v, the operation
only removes one of them, and the rest becomes self-loops.
Let S be a subset of edges. A subset X ⊆ V is called a subset feedback vertex set if G − X
has no simple cycle passing through an edge of S, or equivalently, the graph obtained from G − X
by contracting every edge e ∈ E[V \ X] \ S is a forest. Similarly, we call X a subset pseudoforest
deletion set if the graph obtained from G − X by contracting every edge e ∈ E[V \ X] \ S is a
pseudoforest.
Subset Pseudoforest Deletion
Parameter: k
Input: A graph G = (V, E), a set S ⊆ E, and an integer k.
Question: Is there a set X ⊆ V of at most k vertices such that the graph obtained from
G − X by contracting every edge e ∈ E[V \ X] \ S is a pseudoforest?
40

This problem can be expressed as 0/1/all Deletion as follows. Every vertex v has the same
domain D(v) = S. We introduce a two-fan constraint (ϕ(u) = e) ∨ (ϕ(v) = e) for every edge
e = uv ∈ S. We also introduce an equality (identity permutation) constraint ϕ(u) = ϕ(v) for every
edge uv 6∈ S. Let C be the obtained set of constraints. If C[V 0 ] has no two-fan constraints for
some V 0 ⊆ V , (C[V 0 ], ϕ∅ ) has a deletion set of size zero. Therefore, we can use the same choice
of branching sets as for Two-fan Deletion. Thus, the algorithm runs in O(4k km) time. The
correctness of the expression follows from the following lemma.
Lemma 24. Let G = (V, E) be a graph with a subset S ⊆ E and let C be the corresponding set of
0/1/all constraints. Then, the graph obtained by contracting every edge e ∈ E \ S is a pseudoforest
if and only if C is satisfiable.
Proof. We modify C for each contraction of an edge e = uv by removing the constraint Cuv and
replacing every occurrence of u and v by e. When we obtain the graph G0 by contracting every edge
e ∈ E \ S, we also obtain the set C 0 of constraints corresponding to G0 . Because every contracted
edge e = uv has the equality constraint, C is satisfiable if and only if C 0 is satisfiable. From
Lemma 23, C 0 is satisfiable if and only if G0 is a pseudoforest. Therefore, C is satisfiable if and
only if G0 is a pseudoforest.
As mentioned in Section 1.3, Node Multiway Cut is also a special case of our problem.
Node Multiway Cut
Parameter: k
Input: A graph G = (V, E), a set of terminals T ⊆ V , and an integer k.
Question: Is there a set X ⊆ V \ T of size at most k such that every terminal in T lies in a
different connected component of G − X?
This problem can be expressed as 0/1/all Deletion as follows. First, we split each terminal
s ∈ T as follows to make s undeletable: for each edge sv ∈ δ(s), we create a new vertex sv
and replace the edge sv with sv v. Let G0 = (V 0 , E 0 ) be the obtained graph. We introduce a
variable v with D(v) := T for each vertex v ∈ V 0 and an equality (identity permutation) constraint
ϕ(u) = ϕ(v) for each edge uv ∈ E 0 . Finally, we set A = {sv | s ∈ T, sv ∈ δ(s)} and ϕA (sv ) := s.
We can observe that a minimum deletion set X avoiding every sv always exists because each vertex
sv has degree one, and such X is actually a minimum multiway cut.
Let I = (C, ϕA ) be the obtained instance. We can construct a multiway cut of size at most 2|x|
by rounding up a half-integral FI -cover x. Therefore, we have k − c(I) ≤ 21 k. Because the domain
size is |T | = O(n), the naive implementation of the incremental-test oracle runs in a constant time.
Because any I = (C[V 0 ], ϕ∅ ) has a deletion set of size zero, we do not need branching sets. Thus,
1
we can solve Node Multiway Cut in O(22· 2 k km) = O(2k km) time.
We finally show Group Feedback Vertex Set and its applications.
Group Feedback Vertex Set
Parameter: k
Input: A group Γ = (D, ·) given as an O(TΓ )-time oracle performing the group operation (·),
a Γ-labeled graph G = (V, E) with labeling λ : Ê → D with λ(uv) · λ(vu) = 1Γ for every
uv ∈ Ê, where 1Γ is the unity of Γ, and an integer k.
Question: Is there a set X ⊆ V of at most k vertices such that G − X has a consistent
labeling? That is, is there a labeling ϕ : V \ X → D such that ϕ(u) · λ(uv) = ϕ(v) for every
uv ∈ E[V \ X]?

41

This problem can be expressed as 0/1/all Deletion because a function πe (a) := a · λ(e) is a
permutation. Note that G − X has a consistent labeling if and only if it admits no non-zero cycles
(i.e., it admits no cycle (v0 , . . . , v` ) with λ(v0 v1 ) · λ(v1 v2 ) · · · λ(v`−1 v` ) 6= 1Γ ). In contrast to Node
Unique Label Cover, the domain size is not a parameter, and each permutation is given not as a
table of size |D|, but as an O(TΓ )-time oracle answering a · b for given a, b ∈ D. Therefore, the naive
implementation of the incremental-test oracle runs in O(TΓ ) time. We can use the following choice
of a branching set: pick a vertex s and set B := {(s, 1Γ )}. Thus, we can solve Group Feedback
Vertex Set in O(22k km) = O(4k km) time.
Lemma 25. B := {(s, 1Γ )} is a branching set for Group Feedback Vertex Set.
Proof. Let X be a deletion set for I, and let ϕ be an assignment for V \ X satisfying C[V \ X].
If s ∈ X, X is a deletion set for I[s ← 1Γ ]; otherwise, ϕ0 such that ϕ0 (v) := ϕ(v) · ϕ(s)−1 is a
satisfying assignment for C[V \ X] with ϕ0 (s) = 1Γ .
Subset Feedback Vertex Set
Parameter: k
Input: A graph G = (V, E), a set S ⊆ E, and an integer k.
Question: Is there a set X ⊆ V of at most k vertices such that no cycle passes through an
edge of S in G − X?
This problem can be expressed as Group Feedback Vertex Set as follows. We use a group
Γ = (2S , ⊕), where ⊕ is the XOR operator (X ⊕ Y = (X \ Y ) ∪ (Y \ X)). We set λ(e) = {e} for
each edge e ∈ S and λ(e) = ∅ for each edge e ∈ E \ S. Then, a cycle is non-zero if and only if it
contains an edge in S.
The group operation takes O(|S|) = O(m) time. Therefore, the naive implementation of the
incremental-test oracle takes O(m) time. We now provide a constant-time incremental-test oracle
for (C[V 0 ], ϕ{s} ) with ϕ{s} (s) = ∅. We use the following implementation.
U := S ∪ {}.

(
e (e ∈ S)
I(s) = . A(a, e) =
a (e ∈
6 S).

(
true
T (a, b) =
false

(a 6= b)
(a = b).

For a walk W , the function A∗ (W ) returns the last edge of W contained in S or  if W contains
no edges in S. Then, for a single-branching pair (P, Q), we have P 6≡ Q ⇐⇒ the simple cycle
contained in P ◦ Q−1 contains an edge in S ⇐⇒ A∗ (P ) 6= A∗ (Q). Therefore, the abovementioned
implementation is correct. Thus, we can solve Subset Feedback Vertex Set in O(4k km) time.
Non-monochromatic Cycle Transversal
Parameter: k
Input: An edge-colored graph G = (V, E) and an integer k.
Question: Is there a set X ⊆ V of at most k vertices such that G − X contains no nonmonochromatic cycles?
This problem can be expressed as Group Feedback Vertex Set as follows. Let L be the
set of colors, and let c(e) ∈ L denote the color of an edge e. We use the group Γ = (2V ×L , ⊕). We
set λ(e) = {(u, c(e)), (v, c(e))} for each edge e = uv ∈ E. Then, a cycle is non-zero if and only if it
is non-monochromatic.
The naive implementation of the incremental-test oracle takes O(n|L|) = O(nm) time. We
now provide a constant-time incremental-test oracle for (C[V 0 ], ϕ{s} ) with ϕA (s) = ∅. We use the

42

following implementation.
(
true
U := (V × L) ∪ {, ∗}. I(s) = . T (a, b) =
false

A(, sv) = (s, c(sv)).

(∗ =
6 a 6= b 6= ∗)
otherwise.



(w = v ∧ c = c(uv))
∗
A((w, c), uv) = (w, c)
(w =
6 v ∧ c = c(uv))


(u, c(uv)) (c 6= c(uv)).

Let W = (v0 , . . . , v` ) be a walk with ` > 0, and let c = c(v`−1 v` ). A suffix (vi , . . . , v` ) is
called the longest monochromatic suffix of W if c(vj vj+1 ) = c for every j ≥ i and c(vi−1 vi ) 6= c or
i = 0 holds. We can observe that the longest monochromatic suffix of W starts from vi and has the
color c if A∗ (W ) = (vi , c), and the longest monochromatic suffix of W forms a monochromatic cycle
if A∗ (W ) = ∗. Then, for a single-branching pair (P, Q), we have P 6≡ Q ⇐⇒ the simple cycle
contained in P ◦ Q−1 is non-monochromatic ⇐⇒ none of P and Q induces a monochromatic cycle
and the longest monochromatic suffixes of P and Q start from different vertices or have different
colors ⇐⇒ ∗ =
6 A∗ (P ) 6= A∗ (Q) 6= ∗. Therefore, the abovementioned implementation is correct.
Thus, we can solve Non-monochromatic Cycle Transversal in O(4k km) time.

References
[1] M. A. Babenko. A fast algorithm for the path 2-packing problem. Theory of Computing
Systems, 46(1):59–79, 2010.
[2] M. L. Balinski. Integer programming: Methods, uses, computations. Management Science,
12(3):253–313, 1965.
[3] A. Becker, R. Bar-Yehuda, and D. Geiger. Randomized algorithms for the loop cutset problem.
Journal of Artificial Intelligence Research, 12:219–234, 2000.
[4] H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth.
SIAM Journal on Computing, 25(6):1305–1317, 2006.
[5] H. L. Bodlaender, H. Ono, and Y. Otachi. A faster parameterized algorithm for pseudoforest
deletion. In Proceedings of the 11th International Symposium on Parameterized and Exact
Computation (IPEC 2016), pages 7:1–7:12, 2017.
[6] J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node
multiway cut problem. Algorithmica, 55(1):1–13, 2009.
[7] M. C. Cooper, D. A. Cohen, and P. G. Jeavons. Characterising tractable constraints. Artificial
Intelligence, 65(2):347–361, 1994.
[8] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk,
and S. Saurabh. Parameterized Algorithms. Springer International Publishing, 2015.
[9] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized
above lower bounds. ACM Transactions on Computation Theory, 5(1):3–11, 2013.
43

[10] R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer Verlag, 2012.
[11] J. Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, pages 449–467,
1965.
[12] A. Frank and É. Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49–65, 1987.
[13] S. Fujishige and X. Zhang. New algorithms for the intersection problem of submodular systems.
Japan Journal of Industrial and Applied Mathematics, 9(3):369–382, 1992.
[14] N. Garg, V. V. Vazirani, and M. Yannakakis. Multiway cuts in node weighted graphs. Journal
of Algorithms, 50(1):49–61, 2004.
[15] S. Guillemot. FPT algorithms for path-transversal and cycle-transversal problems. Discrete
Optimization, 8(1):61–71, 2011.
[16] H. Hirai. A dual descent algorithm for node-capacitated multiflow problems and its applications. 2015. arXiv:1508.07065.
[17] Y. Iwata. Linear-time kernelization for feedback vertex set. In Proceedings of 44th International
Colloquium on Automata, Languages, and Programming (ICALP), pages 68:1–68:14, 2017.
[18] Y. Iwata, K. Oka, and Y. Yoshida. Linear-time FPT algorithms via network flow. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
1749–1761, 2014.
[19] Y. Iwata, M. Wahlström, and Y. Yoshida. Half-integrality, LP-branching, and FPT algorithms.
SIAM Journal on Computing, 45(4):1377–1411, 2016.
[20] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. Faster
parameterized algorithms using linear programming. ACM Transactions on Algorithms,
11(2):15:1–15:31, 2014.
[21] D. Lokshtanov, M. S. Ramanujan, and S. Saurabh. Linear time parameterized algorithms for
subset feedback vertex set. In Proceedings of 42nd International Colloquium on the Automata,
Languages, and Programming (ICALP), pages 935–946, 2015.
[22] D. Lokshtanov, M. S. Ramanujan, and S. Saurabh. A Linear Time Parameterized Algorithm
for Directed Feedback Vertex Set. 2016. arXiv:1609.04347.
[23] D. Lokshtanov, M. S. Ramanujan, and S. Saurabh. A linear-time parameterized algorithm for
node unique label cover. In Proceedings of the 25th Annual European Symposium on Algorithms
(ESA), pages 57:1–57:15, 2017.
[24] G. Nemhauser and L. Trotter. Vertex packing: structural properties and algorithms. Mathematical Programming, 8:232–248, 1975.
[25] G. Pap. A constructive approach to matching and its generalizations. PhD thesis, Eötvös
Loránd University, 2006.

44

[26] G. Pap. Packing non-returning A-paths. Combinatorica, 27(2):247–251, 2007.
[27] G. Pap. Some new results on node-capacitated packing of A-paths. In Proceedings of the 39th
Annual ACM Symposium on Theory of Computing (STOC), pages 599–604, 2007.
[28] G. Pap. Packing non-returning A-paths algorithmically. Discrete Mathematics, 308(8):1472–
1488, 2008.
[29] G. Pap. Strongly polynomial time solvability of integral and half-integral node-capacitated
multiflow problems. Technical report, EGRES Technical Report, TR-2008-12, Eötvös Loránd
University, 2008.
[30] J.-C. Picard and M. Queyranne. On the structure of all minimum cuts in a network and
applications. In Combinatorial Optimization II, volume 13 of Mathematical Programming
Studies, pages 8–16. Springer Berlin Heidelberg, 1980.
[31] M. S. Ramanujan and S. Saurabh. Linear time parameterized algorithms via skew-symmetric
multicuts. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1739–1748, 2014.
[32] A. Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer
Science & Business Media, 2002.
[33] M. Wahlström. LP-branching algorithms based on biased graphs. In Proceedings of the 28th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1559–1570, 2017.
[34] Y. Yamaguchi. Packing A-paths in group-labelled graphs via linear matroid parity. SIAM
Journal on Discrete Mathematics, 30(1):474–492, 2016.

45

A

Proof of Persistency

First, we review the results of [19]. Let D be a set containing a special element ⊥, and let
DI := D \ {⊥}. Consider a poset on D such that ⊥ < a for every a ∈ DI and all the other
pairs (a, b) with a 6= b are not comparable. Let a u b be a binary operator that returns the
minimum of a and b if they are comparable and returns ⊥ otherwise. Similarly, let a t b be a binary
operator that returns the maximum of a and b if they are comparable and returns ⊥ otherwise. We
define a · b := (a1 · b1 , . . . , an · bn ) for a binary operator (·) and tuples of elements a = (a1 , . . . , an ),
b = (b1 , . . . , bn ) ∈ Dn . Each index i herein might have a distinct domain Di containing ⊥, and Dn
is an abbreviation for D1 × D2 × . . . × Dn . A function f : Dn → R is called k-submodular if the
following inequality holds for any pair of inputs a, b ∈ Dn :
f (a) + f (b) ≥ f (a u b) + f (a t b).
We denote the restriction of a function f : Dn → R to the domain DIn by fI .
Lemma 26 ( [19]). For a k-submodular function f : Dn → R and a minimizer b ∈ Dn of f , there
exists a minimizer a ∈ DIn of fI such that ai = bi for every i with bi 6= ⊥.
Lemma 27 ( [19]). The following three functions are k-submodular.
• For a permutation π on DI , a function pπ : D × D → {0, ∞} defined as
(
0
if (x = y = ⊥) ∨ (x, y ∈ DI ∧ π(x) = y),
pπ (x, y) =
∞ otherwise.
• For elements a, b ∈ DI , a function ta,b : D × D → {0, ∞} defined as
(
0
if (x = y = ⊥) ∨ (x = a) ∨ (y = b),
ta,b (x, y) =
∞ otherwise.
• A function e : Dr → {0, 21 , 1} defined as


0
e(x) = 1

1
2

if x1 = x2 = · · · = xr ,
if ∃i, j such that ⊥ =
6 xi 6= xj 6= ⊥,
otherwise.

Proof of Theorem 1. Let f : DÊ → R be a function obtained by taking the sum of the following
functions. Each variable uv ∈ Ê here has a domain D(u)∪{⊥}. We add the function pπ on (uv, vu)
for each permutation constraint π(ϕ(u)) = ϕ(v) of C. We add the function ta,b on (uv, vu) for each
two-fan constraint (ϕ(u) = a) ∨ (ϕ(v) = b) of C. Meanwhile, we add the d-ary function e on δ(v)
for each variable v ∈ V \ A, where d = |δ(v)| is the degree of v. Similarly for each variable v ∈ A,
we add the (d + 1)-ary function e on δ(v) with one argument fixed to ϕ(v) (hence it acts as a d-ary
function), where d = |δ(v)|. Then, from Lemma 27, f is k-submodular.
We first observe that we can convert an input b ∈ DÊ of f with f (b) < ∞ to a half-integral
FC,ϕA -cover x with x(V ) = f (b) and convert a half-integral FC,ϕA -cover x to an input b ∈ DÊ
46

with f (b) ≤ x(V ). For each vertex v, we denote by fv (b) the value of the function e for v, that
is, for v ∈ V \ A, fv (b) := e(b|δ(v) ), where
P b|δ(v) is the restriction of b to δ(v), and for v ∈ A,
fv (b) := e(b|δ(v) , ϕA (v)). We have f (b) = v∈V fv (b) when f (b) < ∞.
Let b ∈ DÊ be an input of f with f (b) < ∞. We construct x by setting x(v) = fv (b) for each
v ∈ V . To see that x is a (half-integral) FC,ϕA -cover, take a ϕA -conflicting walk W = (v0 , . . . , v` )
with v0 , v` ∈ A. Now, consider a sequence of variables for f along the walk W :
v0 v1 , v1 v0 , v1 v2 , v2 v1 , . . . , v`−2 v`−1 , v`−1 v`−2 , v`−1 v` , v` v`−1 .
Let bv0 v−1 = ϕA (v0 ) and bv` v`+1 = ϕA (v` ). As the walk P is ϕA -conflicting, we must have an index
0 ≤ i ≤ ` such that ⊥ =
6 bvi vi−1 6= bvi vi+1 6= ⊥ or two indices 0 ≤ i < j ≤ ` such that bvi vi−1 6= ⊥,
bvi vi+1 = ⊥, bvj−1 vj = ⊥, and bvj vj+1 6= ⊥. In both cases, x(V (P )) ≥ 1.
Next, let x be a half-integral FC,ϕA -cover. Let ϕR(x) be the satisfying assignment for C[R(x)].
We then define an input b for f as follows:


if u ∈ R(x),
ϕR(x) (u)
buv = Cvu (ϕR(x) (v)) if u 6∈ R(x), v ∈ R(x), and Cvu (ϕR(x) (v)) 6= all,


⊥
otherwise.
We have f (b) < ∞ from the construction. For every vertex u ∈ V with x(u) = 0, we have
buv = ϕR(x) (u) for every uv ∈ δ(u) if u ∈ R(x). Otherwise, we have buv = ⊥ for every uv ∈ δ(u).
We have fv (b) = 0 in both cases. For any vertex u ∈ V with x(u) = 21 , there exist no edges
uv1 , uv2 ∈ δ(u) such that ⊥ =
6 buv1 6= buv2 6= ⊥ because, otherwise, there exists a ϕA -conflicting
walk W with x(V (W )) = x(u) = 21 < 1, which is a contradiction. Thus, we have f (b) ≤ x(V ).
Now, we prove the claim. Let x be a minimum half-integral FC,ϕA -cover. We then construct
a minimizer b ∈ DÊ of f with f (b) = x(V ). From Lemma 26, there is a minimizer a ∈ DIÊ of fI
such that auv = buv for every uv ∈ Ê with buv 6= ⊥. From the construction above, this means the
existence of the desired deletion set X := {v ∈ V | fv (a) = 1}.

B

Axiomatic Model

We introduce an equivalent formulation of conflicting/implicational walks. The merit of this formulation is that checking whether a set of walks satisfies the conditions below is often easier than
finding an explicit expression as 0/1/all constraints.
Definition 6. A pair (F, F ∗ ) of (possibly infinite) sets of walks in the same graph is called nice if
it satisfies the following conditions.
1. F ⊆ F ∗ .
2. F ∗ is closed under taking a prefix (i.e., for any walk W ∈ F ∗ and any prefix-subwalk P of
W , P ∈ F ∗ holds).
3. For two walks P, Q ∈ F ∗ ending at the same vertex, we write P ≡ Q if and only if P ◦Q−1 6∈ F.
The relation (≡) then becomes an equivalence relation, that is, (1) P ≡ P , (2) P ≡ Q ⇐⇒
Q ≡ P , and (3) P ≡ Q ∧ Q ≡ R =⇒ P ≡ R hold for every walks P, Q, R ∈ F ∗ ending at the
same vertex.
47

4. For any equivalent walks P, Q ∈ F ∗ ending at u and any edge uv ∈ E, P ◦ uv ∈ F ∗ if and
only if Q ◦ uv ∈ F ∗ .
For two walks P, Q ∈ F ∗ ending at the same vertex, we write P 6≡ Q if and only if P ◦ Q−1 ∈ F.
The notations P ≡ Q or P 6≡ Q implicitly imply that P, Q ∈ F ∗ and t(P ) = t(Q). Note that, from
the definition, P ∈ F ⇐⇒ P −1 ∈ F always holds. However, P ∈ F ∗ ⇐⇒ P −1 ∈ F ∗ may not
hold. When F ∗ is the set of all walks starting from a set of vertices A, (F, F ∗ ) is nice if and only
if F is the set of non-returning A-walks (cf. [25, pp. 109–111]).
Lemma 28. Let F ∗ be the set of all implicational walks and let F be the set of all conflicting walks.
Then (F, F ∗ ) is nice.
Proof. Conditions 1, 2, and 4 are trivial from the definition, and we only prove Condition 3.
From Lemma 1, for any two walks P, Q ∈ F ∗ ending at the same vertex, P ≡ Q if and only if
imp(P ) = imp(Q) holds. Therefore, (≡) is an equivalence relation.
Lemma 29. For any nice pair (F, F ∗ ) for a graph G = (V, E), there exist domains for V , 0/1/all
constraints for E, and a partial assignment ϕA for some A ⊆ V such that F is exactly the set of
all ϕA -conflicting walks and F ∗ is exactly the set of all ϕA -implicational walks.
Proof. For each vertex v ∈ V , let D(v) be the classes of equivalent walks in F ∗ ending at v. We
denote the class containing W by [W ] ∈ D(v). Let A := {v | (v) ∈ F ∗ } and ϕA (v) := [(v)]. For
each edge uv ∈ Ê, we define a subdomain D(uv) ⊆ D(u) and a function fuv : D(uv) → D(v) as
follows.
1. For any walk W ∈ F ∗ ending at u, [W ] ∈ D(uv) if and only if W ◦ uv ∈ F ∗ .
2. For any walk W ◦ uv ∈ F ∗ , fuv ([W ]) = [W ◦ uv] holds.
Claim 11. D(uv) and fuv are well-defined.
Proof. Let W 0 ∈ [W ]. We have W 0 ◦ uv ∈ F ∗ if W ◦ uv ∈ F ∗ (by Condition 4).
Suppose that W 0 ◦ uv 6≡ W ◦ uv, which implies W 0 6≡ W ◦ uv ◦ vu. Meanwhile, by Condition
3-(1), W ◦ uv ≡ W ◦ uv holds and, hence, W ◦ uv ◦ vu ≡ W . Thus, we have W 0 6≡ W ◦ uv ◦ vu ≡ W ,
which is a contradiction.
Claim 12. If fuv ([W ]) ∈ D(vu) holds for some class [W ] ∈ D(uv), we have D(u) = D(uv),
−1 .
D(v) = D(vu), and fuv = fvu
Proof. We have fvu (fuv ([W ])) = [W ◦ uv ◦ vu] = [W ] because W ◦ uv ◦ vu ≡ W holds. Suppose
that there exists a class [W 0 ] ∈ D(u) \ D(uv) (i.e., W 0 ◦ uv 6∈ F ∗ ).
Since [W 0 ] 6= [W ] ∈ D(uv), we have W 0 6≡ W ≡ W ◦ uv ◦ vu, implying W 0 ◦ uv ∈ F ∗ , which is a
contradiction. Therefore, we have D(u) = D(uv). By the same argument, we have D(v) = D(vu).
Thus, the claim holds.
Claim 13. If fuv ([W ]) 6∈ D(vu) holds for some class [W ] ∈ D(uv), there exist classes a ∈ D(u)
and b ∈ D(v) such that D(uv) = D(u) \ {a}, D(vu) = D(v) \ {b}, fuv (a0 ) = b for every class
a0 ∈ D(uv), and fvu (b0 ) = a for every class b0 ∈ D(vu).

48

Proof. Let b := fuv ([W ]) 6∈ D(vu). Suppose that there exists a class [W 0 ] ∈ D(uv) such that
fuv ([W 0 ]) 6= fuv ([W ]). Because W ◦ uv 6≡ W 0 ◦ uv holds, we have W ◦ uv ◦ vu ∈ F ∗ , which is a
contradiction. Therefore, we have fuv (a0 ) = b for every class a0 ∈ D(uv). Let [Q] ∈ D(v) \ {b}.
Because Q 6≡ W ◦ uv holds, we have Q ◦ vu ∈ F ∗ . Therefore, we have D(vu) = D(v) \ {b}.
Pick an arbitrary class b0 ∈ D(vu). If a := fvu (b0 ) ∈ D(uv), from Claim 12, we have D(vu) =
D(v), which is a contradiction. Therefore, by the same argument, we have D(uv) = D(u) \ {a} and
fvu (b0 ) = a for every class b0 ∈ D(vu).
Now, we prove the lemma. We introduce a constraint for each edge uv ∈ E as follows: Pick an
arbitrary class c ∈ D(uv). If fuv (c) ∈ D(vu) holds, from Claim 12, the edge uv can be expressed
as fuv (ϕ(u)) = ϕ(v) for the permutation fuv . If fuv (c) 6∈ D(vu) holds, from Claim 13, the edge uv
can be expressed as (ϕ(u) = a) ∨ (ϕ(v) = b) for some classes a ∈ D(u) and b ∈ D(v).

49

