285 research outputs found
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
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
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
Improved hardness for H-colourings of G-colourable graphs
No full textWe present new results on approximate colourings of graphs and, more generally, approximate H-colourings and promise constraint satisfaction problems.
First, we show NP-hardness of colouring k-colourable graphs with colours for every k ≥ 4. This improves the result of Bulín, Krokhin, and Opršal [STOC'19], who gave NP-hardness of colouring k-colourable graphs with 2k – 1 colours for k ≥ 3, and the result of Huang [APPROX-RANDOM'13], who gave NP-hardness of colouring k-colourable graphs with colours for sufficiently large k. Thus, for k ≥ 4, we improve from known linear/sub-exponential gaps to exponential gaps.
Second, we show that the topology of the box complex of H alone determines whether H-colouring of G-colourable graphs is NP-hard for all (non-bipartite, H-colourable) G. This formalises the topological intuition behind the result of Krokhin and Opršal [FOCS’19] that 3-colouring of G-colourable graphs is NP-hard for all (3-colourable, non-bipartite) G. We use this technique to establish NP-hardness of H-colouring of G-colourable graphs for H that include but go beyond K3, including square-free graphs and circular cliques (leaving K4 and larger cliques open).
Underlying all of our proofs is a very general observation that adjoint functors give reductions between promise constraint satisfaction problems.
The full version [55] containing detailed proofs is available at https://arxiv.org/abs/1907.00872.</p
CMS Production of iron plates in Russia/H Rykaczewski. Barrel situation/H Gerwig. Endcap situation/ D Loveless. Coil situation/D Campi. Review of physics group activities/D Denegri. NOVEL instrumental signatures of GMSB in CMS/G Wrochna
No full textFirst look at leptoquarks in CMS
No full textThis paper presents a study on scalar, second generation leptoquark pair production at LHC. Discovery potential of the CMS detector in the muon-jet decay channel was studied with realistic simulation of background and detector response. The mass reach was found to be ~1.6 TeV for one year of running with luminosity 10^34 cm-2 s-1
CMS Level-1 Trigger for b-physics studies
No full textThe CMS Level-1 Trigger system is described with an emphasis on algorithms useful for b-physics studies. Special algorithm is designed for electrons from b-quark decays. It takes advantage of fine granularity crystal electromagnetic calorimeter. One can achieve 10 GeV and 5 GeV thresholds for single and double electron trigger respectively. The muon trigger combines fast dedicated detectors ( RPC) with precise muon chambers ( Drift Tubes, CSC). They provide a sharp pt cut which can be set at ~8-10 GeV for single muon trigger. The two muon trigger pt cut is limited only by the energy loss in absorber and equal to ~4 GeV in the barrel, decreasing down to ~2 GeV in the endcaps
- …
