5 research outputs found
Distributed Binary Labeling Problems in High-Degree Graphs
No full textPublisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.Balliu et al. (DISC 2020) classified the hardness of solving binary labeling problems with distributed graph algorithms; in these problems the task is to select a subset of edges in a 2-colored tree in which white nodes of degree d and black nodes of degree δ have constraints on the number of selected incident edges. They showed that the deterministic round complexity of any such problem is Od,δ(1), Θd,δ(logn), or Θd,δ(n), or the problem is unsolvable. However, their classification only addresses complexity as a function of n; here Od,δ hides constants that may depend on parameters d and δ. In this work we study the complexity of binary labeling problems as a function of all three parameters: n, d, and δ. To this end, we introduce the family of structurally simple problems, which includes, among others, all binary labeling problems in which cardinality constraints can be represented with a context-free grammar. We classify possible complexities of structurally simple problems. As our main result, we show that if the complexity of a problem falls in the broad class of Θd,δ(logn), then the complexity for each d and δ is always either Θ(logdn), Θ(logδn), or Θ(logn). To prove our upper bounds, we introduce a new, more aggressive version of the rake-and-compress technique that benefits from high-degree nodes.Peer reviewe
Induced Disjoint Paths Without an Induced Minor
No full textInternational audienceWe exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs-which avoids the 1-subdivision of, say, K5 as an induced minor-Induced 2-Disjoint Paths is NP-complete. So, while k-Disjoint Paths, for a fixed k, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for k = 2. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced k-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree.We also leverage our new result to show that there is a fixed subcubic graph H such that deciding if an input graph contains H as an induced subdivision is NP-complete. Until now, all the graphs H for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and the fourth author [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph H without two adjacent degree-3 vertices and such that deciding if an input n-vertex graph contains H as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time 2 Ω ( √ n) . This complements an algorithm running in subexponential time 2 Õ(n 2/3 ) by these authors [SODA '24] under the same technical condition.</p
Induced Disjoint Paths Without an Induced Minor
No full textInternational audienceWe exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs-which avoids the 1-subdivision of, say, K5 as an induced minor-Induced 2-Disjoint Paths is NP-complete. So, while k-Disjoint Paths, for a fixed k, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for k = 2. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced k-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree.We also leverage our new result to show that there is a fixed subcubic graph H such that deciding if an input graph contains H as an induced subdivision is NP-complete. Until now, all the graphs H for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and the fourth author [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph H without two adjacent degree-3 vertices and such that deciding if an input n-vertex graph contains H as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time 2 Ω ( √ n) . This complements an algorithm running in subexponential time 2 Õ(n 2/3 ) by these authors [SODA '24] under the same technical condition.</p
Induced Disjoint Paths Without an Induced Minor
No full textInternational audienceWe exhibit a new obstacle to the nascent algorithmic theory for classes excluding an induced minor. We indeed show that on the class of string graphs-which avoids the 1-subdivision of, say, K5 as an induced minor-Induced 2-Disjoint Paths is NP-complete. So, while k-Disjoint Paths, for a fixed k, is polynomial-time solvable in general graphs, the absence of a graph as an induced minor does not make its induced variant tractable, even for k = 2. This answers a question of Korhonen and Lokshtanov [SODA '24], and complements a polynomial-time algorithm for Induced k-Disjoint Paths in classes of bounded genus by Kobayashi and Kawarabayashi [SODA '09]. In addition to being string graphs, our produced hard instances are subgraphs of a constant power of bounded-degree planar graphs, hence have bounded twin-width and bounded maximum degree.We also leverage our new result to show that there is a fixed subcubic graph H such that deciding if an input graph contains H as an induced subdivision is NP-complete. Until now, all the graphs H for which such a statement was known had a vertex of degree at least 4. This answers a question by Chudnovsky, Seymour, and the fourth author [JCTB '13], and by Le [JGT '19]. Finally we resolve another question of Korhonen and Lokshtanov by exhibiting a subcubic graph H without two adjacent degree-3 vertices and such that deciding if an input n-vertex graph contains H as an induced minor is NP-complete, and unless the Exponential-Time Hypothesis fails, requires time 2 Ω ( √ n) . This complements an algorithm running in subexponential time 2 Õ(n 2/3 ) by these authors [SODA '24] under the same technical condition.</p
