Search

Blocking flows were introduced by Dinic (Soviet Math Doklady 11: 1277–1280, 1970) to speed up the computation of maximum network flows. They have been used in algorithms for problems such as maximum cardinality matching of bipartite graphs Hopcroft and Karp (SIAM J Comput 2(4), 225–231, 1973) and general graphs Micali and Vazirani (in: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 17–27, 1980), maximum weight matching of general graphs Gabow and Tarjan (J ACM 38(4), 815–853, 1991), and many others. The blocking algorithm of Gabow and Tarjan (1991) for matching is based on depth-first search. We extend the depth-first search approach to find f-factors of general multigraphs. Here f is an arbitrary integral-valued function on vertices, an f-matching is a subgraph where every vertex x has degree ≤ f (x) , an f-factor has equality in every degree bound. A set of blocking trails for an f-matching M is a maximal collection A of edge-disjoint augmenting trails such that M ⨁ A ∈ A A is a valid f-matching. Blocking trails are needed in efficient algorithms for maximum cardinality f-matching Huang and Pettie (Algorithmica 84(7): 1952–1992, 2022), maximum weight f-factors/matchings by scaling Duan et al. (In: Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Vol. 168 of LIPIcs, 41:1-41:17, 2020; Gabow (A weight-scaling algorithm for f-factors of multigraphs.arXiv:2010.01102, 2020), and approximate maximum weight f-factors and f-edge covers Huang and Pettie (2022). Since these algorithms find many sets of blocking trails, the time to find blocking trails is a dominant factor in the running time. Our blocking trail algorithm runs in linear time O(m). In independent work and using a different approach, Huang and Pettie (2022) present a blocking trails algorithm using time O (m α (m , n)) . As examples of the time bounds for the above applications, an approximate maximum weight f-factor is found in time O (m α (m , n)) using Huang and Pettie (2022), and our algorithm eliminates the factor α (m , n) . Similarly a maximum weight f-factor is found in time O (Φ log Φ m α (m , n) log (Φ W)) using Huang and Pettie (2022) , ( Φ = ∑ v ∈ V f (v) , W the maximum edge weight) and our algorithm eliminates the α (m , n) factor, making the time within a factor log Φ of the bound for bipartite multigraphs. The technical difficulty for this work stems from the fact that a fixed vertex can occur many times in a given search. This does not occur in ordinary matching or in algorithms for maximum cardinality or maximum weight f-matching. These multiple occurrences can create a new variant of blossom, the "skew blossom". Also they can make blossoms become "incomplete", i.e., partially processed yet still relevant in future searches. [ABSTRACT FROM AUTHOR]

The challenge for graph matching algorithms is to extend known time bounds for bipartite graphs to general graphs. We discuss combinatorial algorithms for finding a maximum weight f-factor on an arbitrary multigraph, for given integral weights of magnitude at most W. (An f-factor is a subgraph whose degree function is the given function f : V → N .) For simple bipartite graphs the best-known time bound for combinatorial algorithms is O (n 2 / 3 m log n W) [Gabow and Tarjan, SIAM J Comput 18(5):1013–1036, 1989; n and m are respectively the number of vertices and edges.] A recent algorithm of Duan et al. [in: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020] for f-factors of simple general graphs comes within logarithmic factors of this bound, O ~ (n 2 / 3 m log W) . The best-known bound for bipartite multigraphs is O (Φ m log Φ W) ( Φ ≤ m is the size of the f-factor, Φ = ∑ v ∈ V f (v) / 2 ). This bound is more general than the restriction to simple graphs, and is even superior on "small" simple graphs, i.e., Φ = o (n 4 / 3) . We present an algorithm that comes within a log Φ factor of this bound, i.e., O (Φ log Φ m log Φ W) . The algorithm is a direct generalization of the algorithm of Gabow and Tarjan [J ACM 38(4):815–853, 1991] for the special case of ordinary matching ( f ≡ 1 ). We present that algorithm first. Our analysis is a simplified and more concrete version of Gabow and Tarjan [J ACM 38(4):815–853, 1991] and has independent interest. Furthermore the algorithm and analysis are both incorporated, without modification, into the f-factor algorithm. To extend these ideas to f-factors, the first step is "expanding" edges (i.e., replacing an edge by a length 3 alternating path). Duan et al. [in: Proc. of the 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), 2020] uses a one-time expansion of the entire graph. In contrast, our algorithm keeps the graph small by only expanding selected edges (edges incident to blossoms, in "I(B) sets"). Expanded edges get "compressed" back to their source when no longer needed. Expansion necessitates using an alternate graph model for blossoms (we call them "e-blossoms"). Compression requires coordinating e-blossoms with standard blossoms. [ABSTRACT FROM AUTHOR]

For any odd t ≥ 9 , we present a polynomial-time algorithm that solves the 3-colouring problem, and finds a 3-colouring if one exists, in P t -free graphs of odd girth at least t - 2 . In particular, our algorithm works for (P 9 , C 3 , C 5) -free graphs, thus making progress towards determining the complexity of 3-colouring in P t -free graphs, which is open for t ≥ 8 . [ABSTRACT FROM AUTHOR]

Consider a secure environment (say an airport) that has a unique entry and a unique exit point with multiple inter-crossing paths between them. We want to place (minimum number of) trackers (or check points) at some specific intersections so that based on the sequence of trackers a person has encountered, we can identify the exact path traversed by the person. Motivated by such applications, we study the Tracking Paths problem in this paper. Given an undirected graph with a source s, a destination t and a non-negative integer k, the goal is to find a set of at most k vertices, a tracking set, that intersects each s–t path in a unique sequence. Such a set enables a central controller to track all the paths from s to t. We first show that the problem is NP-complete. Then we show that finding a tracking set of size at most k is fixed-parameter tractable when parameterized by the solution size. More specifically, given an undirected graph on n vertices and an integer k, we give a polynomial time algorithm that either determines that the graph cannot be tracked by k trackers or produces an equivalent instance with O (k 7) edges. [ABSTRACT FROM AUTHOR]

In the classical binary search in a path the aim is to detect an unknown target by asking as few queries as possible, where each query reveals the direction to the target. This binary search algorithm has been recently extended by Emamjomeh-Zadeh et al. (in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC 2016, Cambridge, pp. 519–532, 2016) to the problem of detecting a target in an arbitrary graph. Similarly to the classical case in the path, the algorithm of Emamjomeh-Zadeh et al. maintains a candidates' set for the target, while each query asks an appropriately chosen vertex—the "median"—which minimises a potential Φ among the vertices of the candidates' set. In this paper we address three open questions posed by Emamjomeh-Zadeh et al., namely (a) detecting a target when the query response is a direction to an approximately shortest path to the target, (b) detecting a target when querying a vertex that is an approximate median of the current candidates' set (instead of an exact one), and (c) detecting multiple targets, for which to the best of our knowledge no progress has been made so far. We resolve questions (a) and (b) by providing appropriate upper and lower bounds, as well as a new potential Γ that guarantees efficient target detection even by querying an approximate median each time. With respect to (c), we initiate a systematic study for detecting two targets in graphs and we identify sufficient conditions on the queries that allow for strong (linear) lower bounds and strong (polylogarithmic) upper bounds for the number of queries. All of our positive results can be derived using our new potential Γ that allows querying approximate medians. [ABSTRACT FROM AUTHOR]

In this paper, we study variants of the classical geometric shortest path problem inside a simple polygon, where we allow a part of the path to go outside the polygon. Let P be a simple polygon consisting of n vertices and let s, t be a pair of points in P. Let int(P) represent the interior of P and let P¯ represent the exterior of P, i.e. int(P)=P\∂(P) and P¯=R2\int(P). For an integer k≥0, we define a k-violation path from s to t to be a path connecting s and t such that its intersection with P¯ consists of at most k segments. There is no restriction in terms of the number of segments of the path within P. The objective is to compute a path of minimum Euclidean length among all possible (≤k)-violation paths from s to t. In this paper, we study this problem for k=1 and propose an algorithm that computes the shortest one-violation path in O(n3) time. We show that for rectilinear polygons, the minimum length rectilinear one-violation path can be computed in O(nlogn) time. We extend the concept of one-violation path to a one-stretch violation path. In this case, the path between s and t is composed of (a) a path in P from s to a vertex u of P, (b) a path in P¯ between u and a vertex v of P, and (c) a path in P between v and t. We show that a minimum length one-stretch violation path can be computed in O(nlognloglogn) time. Next, we introduce one- and two-violation monotone rectilinear path problems among a set of n disjoint axis-parallel rectangular objects. Let s, t be two points in R2 that are not in the interior of any of the objects. In the case of one-violation monotone path problem, the desired rectilinear path from s to t consists of horizontal edges that are directed towards the right and vertical edges that are directed upwards, except for at most one edge. Similarly, in the case of a two-violation monotone path problem, all horizontal edges are directed towards the right except at most one and all vertical edges are directed upwards except at most one. Our algorithms for both of these problems run in O(nlogn) time. [ABSTRACT FROM AUTHOR]

Given an undirected, edge-weighted graph G together with pairs of vertices, called pairs of terminals, the minimum multicut problem asks for a minimum-weight set of edges such that, after deleting these edges, the two terminals of each pair belong to different connected components of the graph. Relying on topological techniques, we provide a polynomial-time algorithm for this problem in the case where G is embedded on a fixed surface of genus g (e.g., when G is planar) and has a fixed number t of terminals. The running time is a polynomial of degree $$O\big (\sqrt{g^2+gt}\big )$$ in the input size. In the planar case, our result corrects an error in an extended abstract by Bentz (Int. Workshop on Parameterized and Exact Computation, 109-119, 2012). The minimum multicut problem is also a generalization of the multiway cut problem, a.k.a. multiterminal cut problem; even for this special case, no dedicated algorithm was known for graphs embedded on surfaces. [ABSTRACT FROM AUTHOR]

A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., Parameterized and exact computation, Springer, Berlin, pp. 162-173, 2004), which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is $$\mathsf {FPT}$$ when parameterized by elimination distance to bounded degree, extending results of Bouland et al. (Parameterized and exact computation, Springer, Berlin, pp. 218-230, 2012). [ABSTRACT FROM AUTHOR]

A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery-a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( $$2-\epsilon $$ )-competitive algorithm for convergecast or for broadcast in the class of lines, for any $$\epsilon >0$$ . [ABSTRACT FROM AUTHOR]

We present here a general framework to design algorithms that compute H-join. For a given bipartite graph H, we say that a graph G admits a H-join decomposition or simply a H-join, if the vertices of G can be partitioned in | H| parts connected as in H. This graph H is a kind of pattern, that we want to discover in G. This framework allows us to present fastest known algorithms for the computation of P-join (aka N-join), P-join (aka W-join), C-join (aka 6-join). We also generalize this method to find a homogeneous pair (also known as 2-module), a pair { M, M} such that for every vertex x∉( M∪ M) and i∈{1,2}, x is either adjacent to all vertices in M or to none of them. First used in the context of perfect graphs (Chvátal and Sbihi in Graphs Comb. 3:127-139, ), it is a generalization of splits (a.k.a. 1-joins) and of modules. The algorithmics to compute them appears quite involved. In this paper, we describe an O( mn)-time algorithm computing all maximal homogeneous pairs of a graph, which not only improves a previous bound of O( mn) for finding only one pair (Everett et al. in Discrete Appl. Math. 72:209-218, ), but also uses a nice structural property of homogenous pairs, allowing to compute a canonical decomposition tree for sesquiprime graphs (i.e., graphs G having no module and such that for every vertex v∈ G, G− v also has no module). [ABSTRACT FROM AUTHOR]

Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decomposition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split decomposition algorithm that runs in time O( n+ m) α( n+ m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Compared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algorithms 36(2):205-240, ), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation details are given in this paper. Also, our algorithm extends to circle graph recognition, whereas no such extension is known for Dahlhaus' algorithm. The companion paper (Gioan et al. in , ) uses our algorithm to derive the first sub-quadratic circle graph recognition algorithm. [ABSTRACT FROM AUTHOR]

The reliability polynomial of a graph counts its connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We develop an improved SIS algorithm for estimating the reliability polynomial. The new algorithm runs in expected time O( mlog n α( m, n)) at worst and ≈ m in practice, compared to Θ( m) for the previous algorithm. We analyze the error bounds of this algorithm, including comparison to alternative estimation algorithms. In addition to the theoretical analysis, we discuss methods for estimating the variance and describe experimental results on a variety of random graphs. [ABSTRACT FROM AUTHOR]

The compaction problem is to partition the vertices of an input graph G onto the vertices of a fixed target graph H, such that adjacent vertices of G remain adjacent in H, and every vertex and non-loop edge of H is covered by some vertex and edge of G respectively, i.e., the partition is a homomorphism of G onto H (except the loop edges). Various computational complexity results, including both NP-completeness and polynomial time solvability, have been presented earlier for this problem for various classes of target graphs H. In this paper, we pay attention to the input graphs G, and present polynomial time algorithms for the problem for some class of input graphs, keeping the target graph H general as any reflexive or irreflexive graph. Our algorithms also give insight as for which instances of the input graphs, the problem could possibly be NP-complete for certain target graphs. With the help of our results, we are able to further refine the structure of the input graph that would be necessary for the problem to be possibly NP-complete, when the target graph is a cycle. Thus, when the target graph is a cycle, we enhance the class of input graphs for which the problem is polynomial time solvable. We also present analogous results for a variation of the compaction problem, which we call the vertex-compaction problem. Using our results, we also provide important relationships between compaction, retraction, and vertex-compaction to cycles. [ABSTRACT FROM AUTHOR]

For graph G, let bw( G) denote the branchwidth of G and gm( G) the largest integer g such that G contains a g× g grid as a minor. We show that bw( G)≤3 gm( G) for every planar graph G. This is an improvement over the bound bw( G)≤4 gm( G) due to Robertson, Seymour and Thomas. Our proof is constructive and implies quadratic time constant-factor approximation algorithms for planar graphs for both problems of finding a largest grid minor and of finding an optimal branch-decomposition: (3+ ϵ)-approximation for the former and (2+ ϵ)-approximation for the latter, where ϵ is an arbitrary positive constant. We also study the tightness of the above bound. We show that for any constant c<2, the bound of ${\mathop {\mathrm {bw}}}(G)\leq c\; {\mathop {\mathrm {gm}}}(G) + o({\mathop {\mathrm {gm}}}(G))$ does not hold in general for a planar graph G. [ABSTRACT FROM AUTHOR]

In many applications, the properties of an object being modeled are stored as labels on vertices or edges of a graph. In this paper, we consider succinct representation of labeled graphs. Our main results are the succinct representations of labeled and multi-labeled graphs (we consider planar triangulations, planar graphs and k-page graphs) to support various label queries efficiently. The additional space cost to store the labels is essentially the information-theoretic minimum. As far as we know, our representations are the first succinct representations of labeled graphs. We also have two preliminary results to achieve the main contribution. First, we design a succinct representation of unlabeled planar triangulations to support the rank/select of edges in ccw (counter clockwise) order in addition to the other operations supported in previous work. Second, we design a succinct representation for a k-page graph when k is large to support various navigational operations more efficiently. In particular, we can test the adjacency of two vertices in O(lg k) time, while previous work uses O( k) time. [ABSTRACT FROM AUTHOR]

We obtain the following results related to dynamic versions of the shortest-paths problem: [ABSTRACT FROM AUTHOR]

The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph G=( V, E) into an interval of integers {0,..., k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive O(( k+1)) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006). Furthermore we show that dynamic programming can be used to establish an O(3.8730) algorithm to compute an optimal L(2,1)-labeling. [ABSTRACT FROM AUTHOR]