2,492 research outputs found
PACE Solver Description: Sallow: A Heuristic Algorithm for Treedepth Decompositions
No full textWe describe a heuristic algorithm for computing treedepth decompositions, submitted for the https://pacechallenge.org/2020 challenge. It relies on a variety of greedy algorithms computing elimination orderings, as well as a Divide & Conquer approach on balanced cuts obtained using a from-scratch reimplementation of the 2016 FlowCutter algorithm by Hamann & Strasser [Michael Hamann and Ben Strasser, 2018]
Homomorphism Reconfiguration via Homotopy
No full textWe consider the following problem for a fixed graph H: given a graph G and two H-colorings of G, i.e. homomorphisms from G to H, can one be transformed into the other by changing one color at a time, maintaining an H-coloring throughout.This is the same as finding a path in the Hom(G,H) complex. For H=K_k this is the problem of finding paths between k-colorings, which was recently shown to be in P for k\leq 3 and PSPACE-complete otherwise (Bonsma and Cereceda 2009, Cereceda et al. 2011).
We generalize the positive side of this dichotomy by providing an algorithm that solves the problem in polynomial time for any H with no C_4 subgraph. This gives a large class of constraints for which finding solutions to the Constraint Satisfaction Problem is NP-complete, but paths in the solution space can be found in polynomial time.
The algorithm uses a characterization of possible reconfiguration sequences (that is, paths in Hom(G,H)), whose main part is a purely topological condition described in terms of the fundamental groupoid of H seen as a topological space
On Space Efficiency of Algorithms Working on Structural Decompositions of Graphs
No full textDynamic programming on path and tree decompositions of graphs is a technique that is ubiquitous in the field of parameterized and exponential-time algorithms. However, one of its drawbacks is that the space usage is exponential in the decomposition's width. Following the work of Allender et al. [Theory of Computing, 2014], we investigate whether this space complexity explosion is unavoidable. Using the idea of reparameterization of Cai and Juedes [J. Comput. Syst. Sci., 2003], we prove that the question is closely related to a conjecture that the Longest Common Subsequence problem parameterized by the number of input strings does not admit an algorithm that simultaneously uses XP time and FPT space. Moreover, we complete the complexity landscape sketched for pathwidth and treewidth by Allender et al. by considering the parameter tree-depth. We prove that computations on tree-depth decompositions correspond to a model of non-deterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition's depth. Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomial-time non- deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and tree-depth
Edge Bipartization Faster Than 2^k
No full textIn the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time O(2^k m^2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time O(1.977^k nm), which is the first algorithm with the running time dependence on the parameter better than 2^k. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlström [SODA'14] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree
Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints
No full textWe consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and l columns, x is a vector of l variables, and b is a vector of k integers, we ask whether there exists x in N^l that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and |A|_infty, the largest absolute value of an entry in A, are small.
Papadimitriou [Christos H. Papadimitriou, 1981] was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((|A |_infty + |b|_infty) * k)^O(k^2). This was very recently improved by Eisenbrand and Weismantel [Friedrich Eisenbrand and Robert Weismantel, 2018], who used the Steinitz lemma to design an algorithm with running time (k |A|_infty)^{O(k)}* |b|_infty^2, which was subsequently improved by Jansen and Rohwedder [Klaus Jansen and Lars Rohwedder, 2019] to O(k |A |_infty)^k* log |b|_infty. We prove that for {0,1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2^{o(k log k)}* (l+|{b}|_infty)^{o(k)} would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [Fedor V. Fomin et al., 2018].
We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter {dual treedepth} of the matrix A, denoted td_D(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. [Martin Koutecký et al., 2018] that {ILP Feasibility} can be solved in time |A |_infty^{2^O(td_D(A))} * (k+l+log |b|_infty)^O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and {b} are in {-1,0,1}, the existence of an algorithm with running time 2^{2^o(td_D(A))} * (k+l)^O(1) would contradict the ETH
The Complexity of Promise SAT on Non-Boolean Domains
No full textWhile 3-SAT is NP-hard, 2-SAT is solvable in polynomial time. Austrin, Guruswami, and Håstad [FOCS'14/SICOMP'17] proved a result known as "(2+ε)-SAT is NP-hard". They showed that the problem of distinguishing k-CNF formulas that are g-satisfiable (i.e. some assignment satisfies at least g literals in every clause) from those that are not even 1-satisfiable is NP-hard if g/k < 1/2 and is in P otherwise. We study a generalisation of SAT on arbitrary finite domains, with clauses that are disjunctions of unary constraints, and establish analogous behaviour. Thus we give a dichotomy for a natural fragment of promise constraint satisfaction problems (PCSPs) on arbitrary finite domains
Processed measurement data of acceleration of MR fluid-filled cushion gripper on UR3e robot
No full textThe dataset is a supplement to the article that will soon be submitted for review. DESCRIPTION:The dataset consists of Absolute Orientation Sensor (BNO055) measurements during the transportation of an object by a UR3e robot. The trajectory of the robot's movement includes lifting the object to a height of about 200 mm, horizontal displacement for a distance of 400 mm, and lowering by 200 mm. The transfer procedure begins with the closing of the jaws and ends with their opening. The procedure is analogous to the one outlined in the following dataset:Białek, Marcin, 2023, "Processed measurement data on grip forces during object transportation by a robot using gripper with a MR fluid-filled cushions", https://doi.org/10.18150/B2KCKC, RepOD.The experiment was conducted for three values of acceleration and velocity of the robot joints. For each such configuration, 5 handling tests were carried out.LICENSE:The data are under Creative Commons License CC BY. It is though recommended to manipulate along with the author to fully understand the outcomes. If you have any questions do not hesitate to contact: marcin.bialek@put.poznan.plThis research was funded by the National Science Centre, Poland, grant number: 2021/41/N/ST8/02619. https://ror.org/03ha2q922FILE:"dataset.csv" - processed measurement data obtained during the experiment.For proper interpretation, please refer to the images provided in readme files.COLUMNS: - R_Speed[deg/s] - robot joint movement velocity;- R_Acc[deg/s^2] - robot joint movement acceleration;- SAMPLE[-] - sample number. For each object configuration, acceleration and speed, 5 trials were conducted;- TIME[s] - the measurement time at which the force was recorded;- Linear_X[m/s^2] - X axis of linear acceleration data (acceleration minus gravity)- Linear_Y[m/s^2] - Y axis of linear acceleration data (acceleration minus gravity)- Linear_Z[m/s^2] - Z axis of linear acceleration data (acceleration minus gravity)- Orient_X[deg] - X axis orientation data based on a 360° sphere- Orient_Y[deg] - Y axis orientation data based on a 360° sphere- Orient_Z[deg] - Z axis orientation data based on a 360° sphere- Accl_X[m/s^2] - X axis of acceleration (gravity + linear motion)- Accl_Y[m/s^2] - Y axis of acceleration (gravity + linear motion)- Accl_Z[m/s^2] - Z axis of acceleration (gravity + linear motion)</p
Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings
No full textUsing the algebraic approach to promise constraint satisfaction problems, we establish complexity classifications of three natural variants of hypergraph colourings: standard nonmonochromatic colourings, conflict-free colourings, and linearly-ordered colourings.
Firstly, we show that finding an -colouring of a k-colourable r-uniform hypergraph is NP-hard for all constant 2 ≤ k ≤ and r ≥ 3. This provides a shorter proof of a celebrated result by Dinur et al. [FOCS'02/Combinatorica'05].
Secondly, we show that finding an -conflict-free colouring of an r-uniform hypergraph that admits a k-conflict-free colouring is NP-hard for all constant 2 ≤ k ≤ and r ≥ 4, except for r = 4 and k = 2 (and any ); this case is solvable in polynomial time. The case of r = 3 is the standard nonmonochromatic colouring, and the case of r = 2 is the notoriously difficult open problem of approximate graph colouring.
Thirdly, we show that finding an -linearly-ordered colouring of an r-uniform hypergraph that admits a k-linearly-ordered colouring is NP-hard for all constant 3 ≤ k ≤ and r ≥ 4, thus improving on the results of Nakajima and Živný [ICALP'22/ACM TocT'23]
Turing Kernelization for Finding Long Paths in Graphs Excluding a Topological Minor
No full textThe notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}?
We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle
- …
