Computing the pathwidth of directed graphs with small vertex cover

Computing the pathwidth of directed graphs with small vertex cover

Information Processing Letters 115 (2015) 310–312 Contents lists available at ScienceDirect Information Processing Letters www.elsevier.com/locate/i...

199KB Sizes 0 Downloads 37 Views

Information Processing Letters 115 (2015) 310–312

Contents lists available at ScienceDirect

Information Processing Letters www.elsevier.com/locate/ipl

Computing the pathwidth of directed graphs with small vertex cover Yasuaki Kobayashi Computer Center, Gakushuin University, 1-5-1 Mejiro, Toshima-ku, Tokyo, 171-8588, Japan

a r t i c l e

i n f o

Article history: Received 12 March 2014 Received in revised form 4 August 2014 Accepted 3 October 2014 Available online 8 October 2014 Communicated by Ł. Kowalik Keywords: Graph algorithms Fixed parameter tractable Pathwidth Vertex cover Vertex separation

a b s t r a c t We give an algorithm that computes the pathwidth of a given directed graph D in 3τ ( D ) n O (1) time where n is the number of vertices of D and τ ( D ) is the number of vertices of a minimum vertex cover of the underlying undirected graph of D. This result extends that of [5] for undirected graphs to directed graphs. Moreover, our algorithm is based on a standard dynamic programming with a simple tree-pruning trick, which is extremely simple and easy to implement. An additional advantage of our algorithm is that a minimum vertex cover appears in the analysis but not in the algorithm itself, in contrast to the algorithm of [5] which needs to compute a minimum vertex cover. © 2014 Elsevier B.V. All rights reserved.

1. Introduction Chapelle et al. [5] proved the following theorem. Theorem 1. (See [5].) The pathwidth of an undirected graph G can be computed in 3τ (G ) n O (1) time where n is the number of vertices of G and τ (G ) is the size of a minimum vertex cover of G. The notion of pathwidth is also defined on directed graphs. In this paper, we extend Theorem 1 to directed graphs. Theorem 2. The pathwidth of a directed graph D can be computed in 3τ ( D ) n O (1) time where n is the number of vertices of D and τ ( D ) is the size of a minimum vertex cover of the underlying undirected graph of D. It is known that the pathwidth of an undirected graph G equals the pathwidth of a directed graph G  where

E-mail address: [email protected] http://dx.doi.org/10.1016/j.ipl.2014.10.002 0020-0190/© 2014 Elsevier B.V. All rights reserved.

G  is obtained from G by replacing each edge {u , v } of G by a pair of anti-parallel arcs (u , v ) and ( v , u ) (see [1], for example). Computing pathwidth is NP-hard [7] for undirected graphs and for directed graphs, and is also considered in parameterized complexity. A problem is said to be fixed parameter tractable (FPT) if there is an algorithm for the problem with running time f (k)n O (1) where n is the size of instance and k is a parameter (see [6], for more information). The decision version of the pathwidth problem, deciding whether the pathwidth of a given undirected graph is at most a parameter k, is FPT [2,4]. However, the fixed parameter tractability of the directed case remains unclear. It is only recently that XP algorithms for the decision problem on directed graphs are found by [12,10]. The algorithm of [4] is, in fact, an FPT algorithm for pathwidth parameterized by treewidth. The running time is, however, somewhat large even when the treewidth of an input graph is small. It is natural to ask whether there is a faster FPT algorithm for pathwidth using more restricted parameters such as vertex cover number. Chapelle et al. [5] positively answered this question by proving Theorem 1.

Y. Kobayashi / Information Processing Letters 115 (2015) 310–312

Our result is along this line. We give an FPT algorithm that computes the pathwidth of a given directed graph parameterized by vertex cover number. Our algorithm is a standard dynamic programming for vertex ordering problems [3] with a simple tree-pruning trick (some variants of this trick can be found in the recent work for exact algorithms for pathwidth [9,11,12]). Although our analysis is basically based on the same idea with [5], our algorithm is much simpler than theirs. In particular, we stress that our algorithm uses a vertex cover in the analysis but not in the algorithm, while the algorithm of [5] uses a vertex cover explicitly. This is a considerable advantage from the implementation point of view. Moreover, our algorithm works on undirected and directed graphs. Although the algorithm of [5] is probably extendable to directed graphs, working out the details for such an extension would be a non-trivial task. Our algorithm is essentially for undirected graphs as special case. On the other hand, [5] not only proved Theorem 1 but also gave an FPT algorithm for treewidth parameterized by vertex cover number. 2. Preliminaries Let D = ( V , A ) be a directed graph with n = | V |. For a vertex x ∈ V , we denote by N − (x) the set of in-neighbors of x in D and, for X ⊆ V  , by N − ( X ) the set of in-neighbors of X in D, i.e. N − ( X ) = x∈ X N − (x) \ X . Let σ be a sequence of vertices in V . We assume all the sequences of vertices in this paper have no repetition, that is, the vertices in σ are distinct from each other. The length of σ is denoted by |σ |. We will write the sequence as a list of vertices σ = ( v 1 , v 2 , . . . , v |σ | ). For 0 ≤ i ≤ |σ |, the prefix of σ of length i, denoted by σi , is the sequence consisting of the first i vertices in σ appearing in the same order as in σ . The set of vertices in σ is denoted by V (σ ). For an integer k, we say σ is k-feasible for D if | N − ( V (σi ))| ≤ k for 1 ≤ i ≤ |σ | and is strongly k-feasible for D if σ is a prefix of a k-feasible sequence τ with V (τ ) = V . We extend these notations to vertex sets: a subset U of V is k-feasible (resp. strongly k-feasible) if there is a k-feasible (resp. strongly k-feasible) sequence σ with V (σ ) = U . We may drop the reference to D when it is clear. The vertex separation number of D is the minimum integer k such that V is k-feasible. For every directed graph D, the vertex separation number of D equals its pathwidth [13] (the undirected version of this fact can be found in [8]). Because of this fact, we work on the vertex separation number. Our algorithm is based on the following standard dynamic programming algorithm. Fix an integer k. It is straightforward to see that a proper subset U ⊂ V is strongly k-feasible if and only if there exists a vertex u ∈ V \ U such that U ∪ {u } is also strongly k-feasible. Given this relation, the vertex separation number of D can be computed in 2n n O (1) time. In order to reduce the running time, we run this dynamic programming only on some subsets of V . To this end, we need the following notions. Let U ⊆ V . We say a vertex v ∈ V \ U is subsumed by U if N − ( v ) ⊆ U ∪ N − (U ). An expansion of U , denoted by U ∗ , is defined by the fol-

311

Algorithm 1 Decides whether V is k-feasible or not. 1: for i = 0 to n do 2: Ri ← {∅}. /*Ri will contain the k-feasible relevant sets of size i.*/ 3: end for 4: Add ∅∗ to R|∅∗ | . 5: for i = 0 to n − 1 do 6: for U ∈ Ri do 7: for v ∈ V \ U such that | N − (U ∪ { v })| ≤ k do 8: Add (U ∪ { v })∗ to R j where j = |(U ∪ { v })∗ |. 9: end for 10: end for 11: end for 12: if Rn is not empty then 13: Output “YES”. 14: else 15: Output “NO”. 16: end if

lowing way: starting from U  ← U , while there is v ∈ V \ U subsumed by U  , add all the vertices in V \ U  subsumed by U  to U  ; U ∗ is U  when this process terminates. We say a subset U of V is relevant if there is no vertex v ∈ V \ U with N − ( v ) ⊆ U ∪ N − (U ), that is, U ∗ = U . The key to our dynamic programming is the following lemma. Lemma 1. Let U be a k-feasible subset of V . Then the expansion U ∗ of U is also k-feasible. Moreover, if U is strongly k-feasible, so is U ∗ . Proof. For the first statement, simply observe that N − (U ∪ W ) ⊆ N − (U ) for every set W of vertices in V \ U that are subsumed by U . By an induction on | W |, U ∪ W is k-feasible for every such W and, by a simple iteration, U ∗ is k-feasible. Suppose next U is strongly k-feasible. When U = U ∗ , the lemma is obvious. Suppose otherwise. There is a vertex v ∈ V \ U such that N − ( v ) ⊆ U ∪ N − (U ). Since U is strongly k-feasible, there is a k-feasible sequence π = ( v 1 , v 2 , . . . , v n ) of D such that V (π|U | ) = U and V (π ) = V . Let j be such that v j = v. Since v ∈ V \ U , we have j > |U |. Let

τ = ( v 1 , v 2 , . . . , v |U | , v j , v |U |+1 , . . . , v j−1 , v j+1 , . . . , v n ). In words, τ is obtained from π by moving v to the position immediately after v |U | . Since πi = τi for 1 ≤ i ≤ |U | and N − ( V (πi ) ∪ { v }) ⊆ N − ( V (πi )) for |U | < i ≤ n, τ is k-feasible and hence U ∪ { v } is strongly k-feasible. A straightforward induction proves the lemma. 2 This lemma is a special case of Lemma 5 in [12]. Similar special cases appeared in [11,9]. 3. Proof of Theorem 2 Given a directed graph D = ( V , A ) with n vertices and an integer k, our algorithm decides whether V is k-feasible or not in 3τ ( D ) n O (1) time where τ ( D ) is the size of a minimum vertex cover of the underlying undirected graph of D. The algorithm uses a straightforward dynamic programming over relevant sets, which is described in Algorithm 1.

312

Y. Kobayashi / Information Processing Letters 115 (2015) 310–312

In the following, we will abuse the notation and let

Ri , 0 ≤ i ≤ n, denote  the final value of the program variable Ri . Let R = 0≤i ≤n Ri . Let us note that every element in R is relevant.

It is easy to see that the running time of our dynamic programming is in |R| · n O (1) . By Lemma 3, |R| is bounded by 3! · 3|C | and hence Theorem 2 follows. Acknowledgements

Lemma 2. Algorithm 1 is correct. Proof. We will show that Rn is not empty if and only if V is k-feasible. By Lemma 1, every element in R is k-feasible. Thus, the only if part holds. Suppose V is k-feasible. Let U be a strongly k-feasible relevant set in R. If U = V , we are done. Suppose U is proper subset of V . As U is strongly k-feasible, there is a vertex v ∈ V \ U such that U ∪ { v } is strongly k-feasible. By Lemma 1, (U ∪ { v })∗ is also strongly k-feasible. Therefore, by an induction argument, Rn must be non-empty. 2 An ordered tripartition of a set X is an ordered triple

( P , Q , R ) such that P , Q , and R are disjoint subsets of X with P ∪ Q ∪ R = X . In what follows, fix a minimum vertex cover C of the underlying undirected graph of D. The next lemma is crucial for our running time analysis. Lemma 3. There is an injective mapping from the relevant subsets of V to the collection of ordered tripartitions of C . Proof. Let ( L , M , R ) be an arbitrary ordered tripartition of C . We claim that v ∈ U if and only if N − ( v ) ⊆ L ∪ M, which proves that U is unique given the tripartition ( L , M , R ) and gets us done. The “only if” part of the claim is straightforward since if v ∈ U then N − ( v ) ⊆ U ∪ N − (U ) and hence N − ( v ) ⊆ L ∪ M as N − ( v ) ⊆ C . For the “if” part, suppose N − ( v ) ⊆ L ∪ M. Then, we have N − ( v ) ⊆ U ∪ N − (U ) and therefore v must be in U , since otherwise v is subsumed by U , contradicting the assumption that U is relevant, i.e., U ∗ = U . 2

The author thanks Hisao Tamaki for his suggestions for improving the presentation of the paper and anonymous referees for valuable comments. References [1] J. Barát, Directed path-width and monotonicity in digraph searching, Graphs Comb. 22 (2) (2006) 161–172. [2] H.L. Bodlaender, A linear-time algorithm for finding treedecompositions of small treewidth, SIAM J. Comput. 25 (6) (1995) 1305–1317. [3] H.L. Bodlaender, F.V. Fomin, A.M.C.A. Koster, D. Kratsch, D.M. Thilikos, A note on exact algorithms for vertex ordering problems on graphs, Theory Comput. Syst. 50 (2) (2012) 420–432. [4] H.L. Bodlaender, T. Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms 21 (2) (1996) 358–402. [5] M. Chapelle, M. Liedloff, I. Todinca, Y. Villanger, Treewidth and pathwidth parameterized by the vertex cover number, in: Proc. of WADS 2013, in: LNCS, vol. 8037, 2013, pp. 232–243. [6] R.G. Downey, M.R. Fellows, Parameterized Complexity, Springer, 1998. [7] T. Kashiwabara, T. Fujisawa, Np-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph, in: Proc. of ISCAS 1979, 1979, pp. 657–660. [8] N.G. Kinnersley, The vertex separation number of a graph equals its path-width, Inf. Process. Lett. 42 (6) (1992) 345–350. [9] K. Kitsunai, Y. Kobayashi, K. Komuro, H. Tamaki, T. Tano, Computing directed pathwidth in O (1.89n ) time, in: Proc. of IPEC 2012, in: LNCS, vol. 7535, 2012, pp. 182–193. [10] H. Nagamochi, Linear layouts in submodular systems, in: Proc. of ISAAC 2012, in: LNCS, vol. 7676, 2012, pp. 475–484. [11] K. Suchan, Y. Villanger, Computing pathwidth faster than 2n , in: Proc. of IWPEC 2009, in: LNCS, vol. 5917, 2009, pp. 324–335. [12] H. Tamaki, A polynomial time algorithm for bounded directed pathwidth, in: Proc. of WG 2011, in: LNCS, vol. 6986, 2011, pp. 331–342. [13] B. Yang, Y. Cao, Digraph searching, directed vertex separation and directed pathwidth, Discrete Appl. Math. 156 (10) (2008) 1822–1837.