Wilson Agri began importing cow mattresses into Europe in 1994 and within four years became determined create an indoor living environment for cows, while replicating the natural pasture and outdoor environment. Wilson Agri focuses on the well-being and happiness of the cow, and only develops and produces products that improve the conditions for the animal. Wilson Agri develops buildings for cows, measuring the animals to ensure correct dimensions.
With more than 15 years in the business of designing dairy buildings, structures and accessories, Wilson Agri has the expertise and experience needed to service clients. Wilson Agri aims to offer comfortable beds, while ensuring fresh air and water, and reducing pressure on cows' hooves. The company's product offerings include cow mattresses, passageway rubber, lights, cubicles, ventilation curtains, and tip-over water drinkers.


Summer is an odd time in Academia. Most people think you are on an extended holiday because you aren't in the office. Whilst I would no way claim to have a terrible job, and I am aware how fortunate I am to hold the position I do, summer is a time of varied demands and opportunities that are hard work and time consuming. Personally, since I finished grading my own students I have undertaken external examining, attended UCAS fairs, attended an academic conference and written my module guides for 2016/17. This is not a defence of Academia or a woe is me self-pitying tirade. This is just a very short collection of things I have noticed on my very recent travels, collected here for my own posterity as much as anything else.
There are many demands unreasonably placed on academics that are part of the increasingly worrying decimation of higher education but I feel that engaging with recruitment is not one of them. I feel that academics and teaching staff being on the ground level talking to prospective students is vital. I don't believe this because of the 'students are customers' mantra.
Two days talking to prospective students at a UCAS fair at the University of Bedfordshire reminded me of so many important aspects of my job. Whilst our institutions want to hammer home the consumerist nature of the student body actually talking to young people (and not so young) at Fairs and on Open Days is invigorating. You are reminded that these are young (and not so young people) making a serious investment of their time and their life, heading down paths that scare them financially and emotionally. Some are investing in their dream, some seeking to find a career that they can be proud of and help them fulfil personal ambitions. All have no idea what they are entering into and those best place to help them understand that are those who will teach them day-to-day, in hand with those who help run the institution on a daily basis, those who make universities 'successful' regardless of what the pay scale says.
I believe academics should be invested in recruitment and greater understand the pressures that young people are under in the contemporary climate and I don't believe that metrics are the best way to do this. I believe in good old fashioned conversation. I believe in stepping forward and greeting tentative young people and helping them understand the decision they are about to make. I believe in having conversations where academics are honest about whether a course or an institution is right for an individual. Not everyone should be at university, not everyone should be at my university. This kind of talk horrifies university sales teams and executive board members but we are talking about the lives of young people. In the war of the metric and the statistic and the survey and the table it's too easy to forget that. Two days a year standing by a table talking to people is a cheap reminder of what really matters.
I am what is classed as an early career academic. I have been in academia for three years since moving from the world of independent filmmaking and film education. It's been a whirlwind of publishing, doctorate completion, teaching, promotions and academic conferences. I still feel out of place and like I will be fired every day. I still get anxious about my teaching and my 'research'. Academic conferences are daunting places and there are certain things that go on that make the situation worse, and it's unprofessionalism.
The lack of preparation by people presenting - not prepping their tech, not knowing how long their talk is - worries me because to me that must echo how people teach. I can tell when someone is nervous and can sympathise, I'm always terrified, and you can tell when someone doesn't really care about the fact that there are other people there - peers on their panel, and an audience in front of them.
I love hearing people talk about their research and I love the springboard nature of academic conferences but it always worries me that people's selfishness will result in the downfall of this prestigious and privileged life.
I know fifteen or twenty minutes isn't a long time, certainly not enough time to cover every idea and angle of a piece of work, but that's the time limit. We are all bound by it. The amount of people who have no concept of how long their presentation is baffles me. How can you not? There are three other people who also need to present, there are four other panel slots and a keynote today alone. Be a community thinker and prepare. Don't go long.
Also, audience members, you have a responsibility. You need to show awareness of the appropriateness of your questions and comments. You need to respect other people and recognise whether your input would be more suited to the buffet line. You need to be aware of your tone, and your language, and respect that if you don't get the answer you want you don't have a license to plough back in and demand another.
These may seem like small gripes or someone throwing their toys out of the pram but over the past couple of years I have seen these kinds of trends and it saddens me. There is always good and bad practice, in everything. What saddens me is how much bad practice persists unchallenged - in these latter cases panel chairs often don't challenge when they should or pay attention to the room.
There's an adage that 'how you do anything, is how you do everything' and I see some value in that idea. Academia is under threat from most sides and selfish complacency is not going to save it. It's time for us all to think of others, the bigger picture, of how the way we do thing represents what we do. I agonise over this and hope I can make a difference in a small way.


text:
Q: C# Generate more exe from one project from your experience is it possible to generate multiple exe from one project? Let me better explain, I have a project where the user, as first action, has to select one "object" (e.g. a book) from a collection and then the GUI starts. I'd like to generate, automatically, also a GUI for each object in case I want to send just a dedicated GUI to dedicated user. Is it possible or I have to insert a project for each "book"?
Thanks a lot

A: I think you may be conflating code and content. Typically in a multiple-book sort of scenario, you'd have a single code base, but several modules of content which the code base is capable of running. In your particular case you'd distribute a single .exe and perhaps a series of media files for each title.
In some cases you need custom behavior for certain content. So that may be why you believe you need separate programs. But the requirement to distribute book-specific behavior could still be achieved with a single main executable and a pluggable framework, e.g. you may wish to distribute one assembly per book, and that assembly could expose a class with a specific interface. But the whole thing would still run within a single .exe.

A: Always think about the architecture.
If you want to create two application which shares a lot of common code, then there are multiple ways to achive this.

*

*Use command line switch to application, on the start of the application on which decide on which mode the application will work on. One exe will swich to different modes accordingly.https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/main-and-command-args/command-line-arguments

*Share the common code in one module (.Net Projec) and create a solution with multiple bootstrap project.
In your visual studio solution you can create multiple projects. https://msdn.microsoft.com/en-us/library/h970wzkb.aspx

redpajama_set_name: RedPajamaStackExchange


text:
Consulting for Co-operatives and Mutuals
The Mutuo Story
The Mutuo Team
Management Consultancy for Mutuals
The All Party Parliamentary Group for Mutuals
Home › Management Consultancy for Mutuals
Consultancy services for established co-operatives and mutuals
As globalisation increases the scrutiny of investor-owned business, co-operatives and mutuals have an opportunity to benefit, as long as they are able to communicate the value of their unique business purpose and member-owned status.
Yet, as they grow and change, the original ownership and governance arrangements in co-operatives and mutuals can often diverge from the current needs of the business.
Co-operatives and mutuals must demonstrate that:
They are distinguished in the marketplace through a clear co-operative and mutual purpose that can secure a competitive advantage against investor-owned rivals
The interests of key groups of people – particularly customers and employees – are appropriately represented to ensure that the business obtains the maximum benefit from their engagement
The representative governance structures are modern and effective, resulting in imaginative and forward-looking decisions, rather than an obstruction to innovation and progress
Consultancy services to establish new Mutuals
Mutuo has 15 years' experience of establishing new co-operative and mutual businesses. As a result, more than 2 million people have become members, for the first time having a voice in their co-operative or mutual.
By creating co-operatives and mutuals in new business sectors, Mutuo has been able to demonstrate to policymakers that member-owned firms can be part of a growing and dynamic business world.
Much of the impetus for this work has been fuelled by a growing political appetite for public sector reform. The new co-operatives and mutuals range from start-ups to spin-outs from the public sector, and conversions of existing businesses into a co-operative and mutual form.
New start-ups include a pre-school children's centre which empowers staff and parents, and the UK's first Youth Mutual, which has pioneered the idea of young people taking a leading role in governing their own organisation.
Spin-outs from the public sector include a wide range of new independent organisations, at arm's length from the state, but committed to public benefit. Sectors include hospitals and other health services, social housing, leisure services, and co-operative schools.
Conversions of commercial businesses have emerged as leaders of significant established enterprises begin to question traditional styles of ownership. Mutuo has worked with a global media brand, the UK Post Office and agricultural producers.
Mutuo is the leading advocate for mutuals, promoting all types of co-operative & mutual business through:
• Public affairs and policy advocacy
• Research and publications
• Management consultancy to establish new mutuals
More about Mutuo | The Mutuo Team
New report: Who Owns Europe? … and why it matters for Progressives
A Manifesto for Mutuals: 2019 General Election Policy
Mutuo launches new influencing strategy for consumer co-ops
Purpose-driven businesses top £130 billion income per annum
© 2020 Mutuo

redpajama_set_name: RedPajamaCommonCrawl


text:
Q: FTP Not Retrieving Complete File I have the following code;
/// <summary>
///   Gets a file
/// </summary>
/// <param name="filename"> The filename to get. </param>
/// <returns> A list, containing each line of the file </returns>
public IEnumerable<string> GetFileLines(string filename)
{
  var list = new List<string>();

  var uri = BuildUri(filename);

  var request = (FtpWebRequest)WebRequest.Create(uri.Uri);
  request.Method = WebRequestMethods.Ftp.DownloadFile;

  using (var resp = (FtpWebResponse)request.GetResponse())
  {
    using (var stream = resp.GetResponseStream())
    {
      Thread.Sleep(10000);
      if (stream != null)
      {
        using (var responseStream = new StreamReader(stream))
        {
          // If we still have characters to process
          while (responseStream.Peek() >= 0)
          {
            var line = responseStream.ReadLine();
            list.Add(line);
          }
        }
      }
    }
  }

  return list;
}

However it is not pulling the whole file from the FTP- it seems to cut off before the end of the file has finished downloading.
Is there anything I can add to extend the time it allows to retrieve the data?
Thanks,
David

A: Instead of responseStream.Peek, use below code (You can also remove Thread.Sleep safely)
string line;
while((line = responseStream.ReadLine())!=null)
{

    list.Add(line);
}


text:
\section{Introduction}
Given a graph $G$ and a positive integer $k$, the classical NP-complete
$k$-Coloring problem asks for an assignment of at most $k$ colors to the vertices of $G$
such that no two
adjacent vertices receive the same color. Such a color assignment is
called a {\em $k$-coloring} or simply a {\em coloring} of $G$.
Under the {\em reconfiguration framework}, we are interested in structural and
algorithmic questions related to the solution space of
the $k$-Coloring problem. In particular, for any graph $G$ and integer $k$,
we can define the {\em $k$-Color Graph $\CC_k(G)$} as follows. The vertex set
of $\CC_k(G)$ corresponds to all $k$-colorings of $G$ and two colorings
are adjacent if and only if they differ on exactly one vertex.
The integer $k$ is also called the {\em number of admissible colors}.
Given two $k$-colorings of $G$, $\alpha$
and $\beta$, the {\em $k$-Color Path} problem asks if there exists a path
in $\CC_k(G)$ from $\alpha$ to $\beta$.
This is a well-studied problem, which is known to be
solvable in polynomial time for $k\le 3$~\cite{CHJ11}.
In addition, it is PSPACE-complete for every constant $k\ge 4$, even
when restricted to bipartite graphs, and PSPACE-complete for $k=4$ for planar bipartite graphs~\cite{BC09}.
However, it can be solved in polynomial time for
any $k$, if $G$ is a $(k-2)$-degenerate
graph~\cite{CHJ08,DFFV06}; see also~\cite{BC09} (planar bipartite graphs are 3-degenerate).

In addition to results on the $k$-Color Path problem, many other results have
been obtained in the setting of $k$-coloring reconfiguration. For the
aforementioned PSPACE-complete cases, examples have been explicitly
constructed where any path from $\alpha$ to $\beta$ has exponential
length~\cite{BC09}. On the other hand, for the polynomial case $k\le 3$, the
diameter of components of $\CC_k(G)$ is known to be polynomial~\cite{CHJ11}.
It has been conjectured that this is also the case for $k$ colors and $k-2$
degenerate graphs~\cite{BC09}. This conjecture has been answered positively
for the subclass of graphs of treewidth $(k-2)$~\cite{BB13}.
The connectedness of $\CC_k(G)$ has been studied in~\cite{CHJ08,CHJ09}.
In particular, deciding whether $\CC_k(G)$ is connected is coNP-complete
for $k=3$ and $G$ bipartite, but can be answered in polynomial time if $G$ is planar and bipartite~\cite{CHJ09}.
One may ask whether a {\em shortest} path from $\alpha$ to $\beta$ can be
found in $\CC_k(G)$. In~\cite{CHJ11}, a polynomial time algorithm for $k=3$
and certain pairs of colorings has been given. Finally, it is known that
for any two $k$-colorings $\alpha$ and $\beta$, $2k-1$ colors suffice to
find a path from $\alpha$ to $\beta$, and that this bound is tight~\cite{Cer07,MH99,Jac97}.

Similar reconfiguration questions can be formulated for almost any
search problem, after defining a (symmetric) adjacency relation between solutions.
Such questions have received considerable attention
in recent literature; see e.g. the survey by Van den Heuvel~\cite{JvdH13}.
In most cases, the complexity behavior of these problems is similar.
For instance, deciding whether a path exists between two solutions
is often PSPACE-hard in general, although polynomial time solvable
restricted cases can be identified. For PSPACE-hard cases, it is not
surprising that shortest paths between solutions can have exponential length.
More surprisingly, for most known polynomial time solvable cases, shortest paths
between solutions have been shown to have polynomial length.
Results of this kind have for instance been obtained e.g. for the
reconfiguration of independent sets~\cite{BKW14,KMM12}, vertex covers~\cite{MNR14},
shortest paths~\cite{Bon13,Bon12FSTTCS,KMM11}, or boolean assignments~\cite{IDHPSUU11}.

These problems are interesting for a variety of reasons.
From an algorithmic standpoint, reconfiguration
problems model dynamic situations in which we seek to transform a solution into
a more desirable one, maintaining feasibility during the process
(see~\cite{Jac97} for such an application of $k$-Color Path). Reconfiguration
also models questions of evolution; it can represent the evolution of a genotype
where only individual mutations are allowed and all genotypes must satisfy a
certain fitness threshold, i.e. be feasible.
Moreover, the study of reconfiguration yields insights into the
structure of the solution space of the underlying problem, crucial for the design of efficient
algorithms. In fact, one of the initial motivations behind such questions was to study
the performance of heuristics \cite{GKMP09} and random sampling methods \cite{CHJ08},
where connectivity and other properties of the solution space play a crucial role.

In many applications of reconfiguration problems, the existence of a
path between two solutions is irrelevant, if every such path has
exponential length. So the more important question is in fact: does there exist
a path between two solutions of length at most $\ell$, for some integer $\ell$?
Such {\em length-bounded} reconfiguration questions have been
considered e.g. in~\cite{Bon13,Bon14,GKMP09,KMM11,MNR14,MNRSS13}.
In some cases where the existence of paths between solutions can
be decided efficiently, one can in fact find {\em shortest} paths efficiently~\cite{Bon13,Bon14,GKMP09}.
On the other hand, NP-hard cases have also been identified~\cite{KMM11,MNR14}.
If we wish to obtain a more detailed picture of the complexity of
length bounded reconfiguration, the setting of parameterized
complexity~\cite{DF97,FG06} is very useful, where we choose $\ell$ as parameter.
A systematic study of the parameterized complexity of
reconfiguration problems was initiated by Mouawad et al~\cite{MNRSS13}.
However, in~\cite{MNRSS13}, only negative results were obtained for
length-bounded reconfiguration: various problems were identified where
the problem was not only NP-hard, but also W[1]-hard, when
parameterized by $\ell$ (or even when parameterized by $k+\ell$, where $k$ is another problem parameter).
In this paper, we give an example of a length bounded
reconfiguration problem that is NP-hard, but admits an FPT algorithm.
Another example, namely vertex cover reconfiguration in graphs of bounded degree, was very
recently obtained by Mouawad et al in~\cite{MNR14}.
\medskip

\noindent
{\em $\ell$-Length $k$-Color Path (\Px):}\\
{\sc Instance:} A graph $G$ on $n$ vertices, nonnegative integers $k$ and $\ell$, and two $k$-colorings $\alpha$ and $\beta$ of $G$.\\
{\sc Question:} Does $\CC_k(G)$ contain a path from $\alpha$ to $\beta$ of length at most $\ell$?

\medskip
In this paper we explore fully how the complexity of the above problem
depends on the problem parameters $k$ and $\ell$. Firstly, \Px\ is easily
observed to be PSPACE-hard in general, for $k\ge 4$: Since there are at
most $k^n$ different $k$-colorings of a graph on $n$ vertices, a path
from $\alpha$ to $\beta$ exists if and only if there exists one of
length at most $k^n$. So setting $\ell=k^n$ yields a trivial
reduction from the PSPACE-hard $k$-Color Path problem to \Px.
Nevertheless, this only establishes {\em weak} PSPACE-hardness, since the
chosen value of $\ell$ is exponential in the instance size.
In other words, if we require that all integers are encoded in unary,
then this is not a polynomial reduction.
And indeed, the complexity status of the problem changes under
that requirement; in that case, \Px\ is easily observed to be in NP.
(If $(G, k, \ell, \alpha, \beta)$ is a yes-instance, then a path of length
$\ell$ in $\CC_k(G)$ from $\alpha$ to $\beta$ is a polynomial certificate.)
In Section~\ref{sec:nphard}, we show that \Px\ is in fact NP-complete when
$\ell$ is encoded in unary, or in other words: it is {\em strongly NP-hard}.
On the positive side, in Section~\ref{sec:fpt}, we show that the
problem can be solved in time
$\Oh(2^{k(\ell+1)}\cdot \ell^\ell\cdot \poly(n))$.
This establishes
that \Px\ is {\em fixed parameter tractable (FPT)}, when parameterized by $k+\ell$.
The reader is referred to the excellent books of Downey and
Fellows~\cite{DF97}, Flum and Grohe~\cite{FG06}, and Niedermeier~\cite{N06} for an introduction to parameterized
complexity.
One may ask whether the problem is still FPT
when only parameterized by $\ell$. We show that this is not
the case (unless W[1]=FPT), by showing that \Px\ is W[1]-hard when
only parameterized by $\ell$. We observe however that a
straightforward branching algorithm can solve the
problem in time $n^{\Oh(\ell)}$, so in polynomial time for
any constant $\ell$. In other words, \Px\ is in XP, parameterized by $\ell$.

\begin{table}
\caption{Summary of the problem complexity and results}
\label{table:summary}
\footnotesize
\begin{tabular}{|l|c|c|c|}
\hline
			& $\ell$ as binary variable & $\ell$ as unary variable & $\ell$ as parameter \\
\hline
$k$ as input variable	& PSPACE-complete	&  NP-complete	& W[1]-hard (*) \\
(unary or binary)	&			&		& in XP (T) \\
\hline
$k$ as parameter & (para-)PSPACE-complete & (para-)NP-complete	& FPT (*) \\
			     & 		&  & (see also~\cite{JKKPP14})\\
\hline
$k\ge 4$ as constant	& PSPACE-complete&NP-complete (*)& FPT		  \\
			&  (T), using~\cite{BC09} &			& 	 	\\
\hline
$k\le 3$ 		& polynomial~\cite{JKKPP14}	& polynomial& polynomial \\
\hline
\end{tabular}
\end{table}

Our results are summarized in Table~\ref{table:summary}. Our main results are marked by (*), and
trivial results are marked with (T). Unmarked results follow immediately from results in an adjacent row or column.
To emphasize the strength of both the negative and positive results, we added rows
for both $k$ constant and $k$ as parameter, even though the complexity is always the same.
The FPT result was also obtained very recently and
independently by Johnson et al~\cite{JKKPP14}, although they use a very different algorithm than ours.
In addition, in~\cite{JKKPP14}, the case $k\le 3$ is considered, and is
shown to be polynomial (as conjectured by Cereceda et al~\cite{CHJ11}).

\section{Preliminaries}
For general graph theoretic definitions, we refer
the reader to the book of Diestel~\cite{D05}.
Unless otherwise stated, we assume that each graph $G$ is a
simple, undirected graph with vertex set $V(G)$ and
edge set $E(G)$, where $|V(G)| = n$ and $|E(G)| = m$.
The {\em open neighborhood} of a vertex $v$ is denoted by $N_G(v) = \{u \mid uv \in E(G)\}$ and the
{\em closed neighborhood} by $N_G[v] = N_G(v) \cup \{v\}$.
For a set of vertices $S \subseteq V(G)$,
we define $N_G(S) = \{v \not\in S \mid uv \in E(G), u \in S\}$ and $N_G[S] = N_G(S) \cup S$.
We drop the subscript $G$ when clear from context.
The subgraph of $G$ induced by $S$ is denoted by $G[S]$, where
$G[S]$ has vertex set $S$ and edge set $\{uv \in E(G) \mid u, v \in S\}$.
The maximum degree of a graph $G$ is denoted by $\Delta(G)$.
Let $u$ and $v$ be vertices in a graph $G$. A {\em pseudowalk} from $u$ to $v$ of
length $\ell$ is a sequence $w_0,\ldots,w_{\ell}$ of vertices in $G$
with $w_0=u$, $w_{\ell}=v$, such that for
every $i\in \{0,\ldots,\ell-1\}$, either $w_i=w_{i+1}$, or $w_iw_{i+1}\in E(G)$.

A {\em $k$-color assignment} for a graph $G$ is a function
$\alpha:V(G)\to \{1,\ldots,k\}$ of {\em colors} to the
vertices of $G$. It is a {\em $k$-coloring} if there are
no edges $uv\in E(G)$ with $\alpha(u)=\alpha(v)$. On the
other hand, if there exists such an edge $uv$, then
this edge is said to give a {\em color conflict}.
A graph that admits a $k$-coloring is called {\em $k$-colorable}.
The minimum $k$ such that $G$ is $k$-colorable is
called the {\em chromatic number} of $G$, denoted by $\chi(G)$.
For a $k$-coloring $\alpha$ of $G$, the set of
colors {\em used by $\alpha$} is
$\{\alpha(v) \mid v\in V(G)\}$.
Pseudowalks in $\CC_k(G)$ from $\alpha$ to $\beta$ are also called
{\em $k$-recoloring sequences} from $\alpha$ to $\beta$.
If there exists an integer $k$ such that $\alpha_0,\ldots,\alpha_m$ is a
$k$-recoloring sequence, then this is called a
{\em recoloring sequence} from $\alpha_0$ to $\alpha_m$.
Clearly, if there exists a $k$-recoloring sequence
from $\alpha$ to $\beta$ of length $\ell$, then $\CC_k(G)$
contains a path from $\alpha$ to $\beta$ of length at most $\ell$.

A {\em $k$-color list assignment} for a graph $G$ is a mapping $L$ that assigns a {\em color list} $L(v)\subseteq \{1,\ldots,k\}$ to each vertex $v\in V(G)$. A $k$-coloring $\alpha$ of $G$ is an {\em $L$-coloring} if $\alpha(v)\in L(v)$ for all $v$. By $\CC(G,L)$ we denote the subgraph of $\CC_k(G)$ induced by all $L$-colorings of $G$, and pseudowalks in $\CC(G,L)$ are called $L$-recoloring sequences. The $\ell$-Length $L$-Color Path (\LR) problem asks, given $G,L,\alpha,\beta,\ell$, where $\alpha$ and $\beta$ are $L$-colorings of $G$, whether there exists an $L$-recoloring sequence from $\alpha$ to $\beta$ of length at most $\ell$.

For a positive integer $k \geq 1$, we denote $[k] = \{1, \ldots , k\}$.
For a function $f:D\to I$ and subset $D'\subseteq D$, we
denote by $f\restr_{D'}$ the restriction of $f$ to the domain $D'$.
The (unique) trivial function with empty domain is denoted by $\emptyfunc$. Note that for any function $g$, $g\restr_{\emptyset}=\emptyfunc$.
We use $\poly(x_1,\ldots,x_p)$ to denote a polynomial function on variables $x_1,\ldots,x_p$.

\section{W[1]-hardness}\label{sec:whard}
We give a reduction from the following problem:

\medskip
\noindent
{\em $t$-Independent Set (\IS):}\\
{\sc Instance:} A graph $G$ and a positive integer $t$.\\
{\sc Question:} Does $G$ have an independent set of size at least $t$?
\medskip

The \IS\ problem is known to be W[1]-hard~\cite{DF97,FG06} when parameterized by $t$.
We will also use the following result, which was shown
independently by Cereceda~\cite{Cer07}, Marcotte and Hansen~\cite{MH99}
and Jacob~\cite{Jac97}: For every pair of $k$-colorings $\alpha$ and $\beta$ of a graph $G$, there exists a path from $\alpha$ to $\beta$ in $\CC_{2k-1}(G)$, and there are examples where at least $2k-1$ colors are necessary.
The graphs constructed in~\cite{Cer07,MH99,Jac97} to prove the
latter result are in fact very similar. We will use these graphs
for our reduction, though we will need a slightly
stronger claim, so we need to restate the proof.
The next definition and proof
follow~\cite[Section~6.1]{Cer07} closely.

For any integer $k \ge 1$, let $B_k= \overline{K_k \times K_k}$ (the complement of
the Cartesian product graph of two complete graphs on $k$ vertices).
More precisely, we let $V(B_k)=\{b^i_j \mid i,j\in\{1,\ldots,k\}\}$, and two vertices $b^i_j$
and $b^{i'}_{j'}$ are adjacent if and only if $i\not=i'$ and $j\not=j'$. Define
two $k$-colorings $\alpha^k$ and $\beta^k$ for $B_k$ by setting
$\alpha^k(b^i_j)=i$ and $\beta^k(b^i_j)=j$ for all vertices $b^i_j$.

\begin{thm}
\label{thm:NeedsManyColors}
For every integer $k\ge 1$, let $B_k$, $\alpha^k$ and $\beta^k$ be as defined above. Then
\begin{enumerate}
 \item
 every recoloring sequence
 from $\alpha^k$ to $\beta^k$ contains a coloring
 that uses at least $2k-1$ different colors, and
 \item there exists a $(2k-1)$-recoloring sequence of length at most $2k^2$ from $\alpha^k$ to $\beta^k$.
\end{enumerate}
\end{thm}

\PF
Consider a recoloring sequence $\gamma_0,\ldots,\gamma_m$ from $\alpha^k$ to $\beta^k$.
For $i\in \{1,\ldots,k\}$, the vertex set $R_i=\{b^i_j\mid j\in \{1,\ldots,k\}\}$
is called a {\em row} of $B_k$. For every $i$, the coloring $\alpha^k$ colors the
vertices of row $R_i$ all with the same color, and $\beta^k$ colors them all
differently. So we may choose the lowest index $j$ such that $\gamma_j$
colors all vertices of at least one row $R_i$ differently.
The choice of $j$ guarantees that for $\gamma_j$, for all other
rows, there exists a color that is used for at least two different
vertices in the row, and thus is not used in any other row (this
follows easily from the definition of $B_k$). We conclude that
$\gamma_j$ uses at least $2k-1$ different colors in total,
which proves the first statement.

\medskip
To obtain a $(2k+1)$-recoloring sequence from $\alpha^k$ to $\beta^k$, we
can apply the following general method (which applies in
fact to any two $k$-colorings of any $k$-colorable graph):
Choose an arbitrary $k$-coloring $\gamma$ of $B_k$. For every
vertex $v\in V(B_k)$ with $\gamma(v)\le k-1$, recolor $v$ to
the color $k+\gamma(v)$ (this is a color in $\{k+1,\ldots,2k-1\}$, so
it is not used by $\alpha^k$ or $\beta^k$). Next, recolor all vertices
$v$ to their target color $\beta(v)$, starting with those vertices $v$ with $\gamma(v)=k$.
It can be verified that this way, a $k$-coloring is maintained
throughout, and that every vertex is recolored at most twice.
\QED

We remark that the distance from $\alpha^k$ to $\beta^k$ in $\CC_{2k-1}(B_k)$ is
in fact strictly smaller than $2k^2$, but we do not need to
know or prove the exact distance. We can now state the
reduction from \IS\ to \Px\ that we use to prove W[1]-hardness.

\paragraph{Construction}
For ease of presentation, we give a reduction from the \ISS\ problem, which
remains W[1]-hard. Given an instance $(G, t - 1)$ of \ISS,
where $G = (V, E)$ and $V = \{v_1, \ldots, v_n\}$, we construct a
graph $G'$ in time polynomial in $n + m + t$ as follows.

$G'$ contains a copy of $G$ and a copy of $B_{t}$ with all edges between them.
In addition, $G'$ contains $n + t + 1$ independent sets
$C_1$, $\ldots$, $C_{n + t + 1}$, each of size $2t + 2t^2$. We say that
$C_i$ (for $1 \leq i \leq n + t + 1$) is a {\em color-guard set}, as it will be
used to enforce some coloring constraints: in the colorings we define, and all colorings reachable from them using at most $|C_i|-1$ recolorings, $C_i$ will contain at least one vertex of color $i$.
We let $V_G = \{g_1, \ldots, g_n\}$, $V_B = \{b^i_j \mid i,j \in \{1, \ldots, t\}\}$,
$V_C = C_1 \cup \ldots \cup C_{n + t + 1}$, and hence $V(G') = V_G \cup V_B \cup V_C$.
The total number of vertices in $G'$ is therefore $n + t^2 + (n + t + 1)(2t + 2t^2)$.
For every vertex $g_i \in V_G$, we add all edges
between $g_i$ and the vertices in $V_C \setminus (C_i \cup C_{n + t + 1})$.
Similarly, for every vertex $b \in V_B$, we add all edges between $b$
and the vertices in $C_{n + t + 1}$.
We define $\alpha$ as follows.
For every vertex $g_i \in V_G$, $1 \leq i \leq n$, we set $\alpha(g_i) = i$.
For every $i\in \{1,\ldots,n + t + 1\}$ and every vertex $c\in C_i$, we set $\alpha(c) = i$.
For every vertex $b^i_j \in V_B$ (with $i,j\in \{1,\ldots,t\}$), we choose $\alpha(b^i_j) = n + i$.

\begin{propo}
\label{prop:colorguard}
Let $G'$ and $\alpha$ be as constructed above, from a graph $G$ on $n$ vertices.
Let $k = n + t + 1$, and
let $\alpha_0, \ldots, \alpha_\ell$ be a $k$-recoloring sequence of length
at most $2t + 2t^2$ with $\alpha_0=\alpha$.
Then for all $g_i \in V_G$ and $0 \leq x \leq \ell$, we have $\alpha_x(g_i) \in \{i, n + t + 1\}$.
Moreover, for all $b \in V_B$ and $0 \leq x \leq \ell$, we have $\alpha_x(b) \neq n + t + 1$.
\end{propo}

\PF
Since every vertex $g_i \in V_G$ is adjacent to all vertices in
$V_C \setminus \{C_i \cup C_{n + t + 1}\}$, and $|C_j| = 2t + 2t^2$ for all $j$,
it follows that if $g_i$ receives a color $j\not\in \{i, n + t + 1\}$, then
all vertices in $C_j$ must have been recolored earlier, which contradicts the fact that we consider a recoloring sequence of length at most $2t + 2t^2$.
Similarly, every vertex $b \in V_B$ is adjacent to all vertices in $C_{n + t + 1}$.
Therefore, if $b$ receives color $n + t + 1$ then all vertices in $C_{n + t + 1}$ must have been recolored first.
\QED

Finally, we define the target coloring $\beta$: for every vertex $v \in V_G \cup V_C$
we set $\beta(v) = \alpha(v)$. For every
vertex $b^i_j \in V_B$ (with $i,j\in \{1,\ldots,t\}$), we choose $\beta(b^i_j) = n + j$.
In other words, the goal is to change from a `row coloring' to a `column coloring' for $V_B$, while maintaining the same coloring for vertices in $V_G \cup V_C$.
The corresponding \Px\ instance is denoted by
$(G', k, \ell, \alpha, \beta)$ with $k = n + t + 1$ and $\ell = 2t + 2t^2$.

\begin{lem}
\label{lem:YESstaysYES:W}
Let $G'$, $k$, $\ell$, $\alpha$, and $\beta$ be as
constructed above, from a graph $G$ on $n$ vertices.
If $G$ has an independent set of size at least $t - 1$,
then $\CC_{k}(G')$ contains a path
from $\alpha$ to $\beta$, of length at most $\ell = 2t + 2t^2$.
\end{lem}

\PF
We let $S$ be an independent
set of size $t - 1$ in $G$. The following recoloring sequence is
an $(n + t + 1)$-recoloring sequence from
$\alpha$ to $\beta$ of length at most $2t + 2t^2$:

\begin{itemize}
\item Assign the vertices in $G'$ corresponding to the vertices in $S$ color $n + t + 1$ (one by one).
By our construction of $G'$, none of these steps will introduce any color
conflicts since vertices in $V_G$ are not connected
to vertices in $C_{n + t + 1}$.
\item From Theorem~\ref{thm:NeedsManyColors}, we know that we can
recolor the vertices in $V_B$ using $2t - 1$ colors and at most $2t^2$ recoloring steps.
Since $t - 1$ vertices have been recolored in the previous step, we can now use
the corresponding $t - 1$ colors to apply the $(2t - 1)$-recoloring
sequence to $V_B$.
\item Recolor the $t - 1$ vertices that were initially recolored
by assigning them their original color again (which is also their target color in $\beta$). None of these steps will introduce any color conflicts since at this point
every vertex in $V_B$ is assigned a color greater than $n$ again.
\end{itemize}

Clearly, the described recoloring sequence consists of
at most $2(t - 1) + 2t^2 < 2t + 2t^2$ recoloring steps.
\QED

\begin{lem}
\label{lem:NOstaysNO:W}
Let $G'$, $k$, $\ell$, $\alpha$, and $\beta$ be as
constructed above, from a graph $G$ on $n$ vertices.
If $\CC_{k}(G')$ contains a path from $\alpha$ to $\beta$ of
length at most $\ell = 2t + 2t^2$, then $G$ has an independent set of size at least $t - 1$.
\end{lem}

\PF
Assume that there exists some
$k$-recoloring sequence from $\alpha$ to $\beta$ of length at most $\ell = 2t + 2t^2$.
Theorem~\ref{thm:NeedsManyColors} shows that this sequence contains a coloring $\gamma$ that assigns at least $2t-1$ different colors to $V_B$.
Let $U=\{\gamma(b) \mid b\in V_B\}$ denote this color set with $|U|\ge 2t-1$.
Vertices in $V_B$ cannot be assigned color $n+t+1$ in a sequence of this length (Proposition~\ref{prop:colorguard}), so $|U\cap \{1,\ldots,n\}|\ge t-1$.
Since $G'$ contains all edges between $V_B$ and $V_G$, we conclude that all vertices in $S=\{g_i\in V_G \mid i\in U\}$ must have $\gamma(g_i)\not=i$, and thus $\gamma(g_i)=n + t + 1$ (Proposition~\ref{prop:colorguard}). It follows that $S$ is an independent set of $G$ of size at least $t-1$.\QED

Combining Lemmas~\ref{lem:YESstaysYES:W} and~\ref{lem:NOstaysNO:W} with the fact that \ISS\ is W[1]-hard yields:

\begin{thm}
$\ell$-Length $k$-Color Path is W[1]-hard when parameterized by $\ell$.
\end{thm}

\section{NP-hardness}\label{sec:nphard}
In this section we show that the \Px\ problem
is strongly NP-hard for every fixed constant $k \geq 4$.
We give a reduction from the following problem which
was shown to be NP-complete by Garey, Johnson, and Stockmeyer~\cite{GJS76}.

\medskip
\noindent
{\em Planar Graph 3-Colorability (\Pz):}\\
{\sc Instance:} A planar graph $G$.\\
{\sc Question:} Is $G$ 3-colorable?
\medskip

In contrast to the previous section, here we construct an instance of
the \LR\ problem.
An instance $G,L,\alpha,\beta,\ell$ of the \LR\ problem with $L(v)\subseteq [4]$ for all $v$ is easily
transformed to an instance of \Px, by adding one complete
graph on four vertices $x_i$ with $i\in [4]$ and $\alpha(x_i)=\beta(x_i)=i$,
and edges $vx_i$ for every vertex $v\in V(G)$ and $i\not\in L(v)$. This yields:

\begin{lem}[\cite{BC09}]
\label{lem:listversion}
For any $k \geq 4$, in polynomial time an \LR\ instance
($G$, $L$, $\ell$, $\alpha$, $\beta$), with color lists $L(v) \subseteq [4]$,
can be transformed into an \Px\ instance ($G'$, $k$, $\ell$, $\alpha'$, $\beta'$), such that the distance
between $\alpha$ and $\beta$ in $\CC(G, L)$ (possibly infinite) is the
same as the distance between $\alpha'$ and $\beta'$ in $\CC_k(G')$.
\end{lem}

We will also make heavy use of the notion of $(a,b)$-forbidding paths
and their properties, which were introduced in~\cite{BC09}.
Informally, these are paths that can be added between any pair
of vertices $u$ and $v$ (provided that $L(u),L(v)\not=[4]$), that
function as a special type of edge, which only excludes the
color combination $(a,b)$ for $u$ and $v$ respectively, but allows (recoloring to) any other color combination.
More precisely, for $a, b \in [4]$, a path $P$ with
color lists $L(x)\subseteq [4]$ for all $x\in V(P)$ and end vertices $u$ and $v$ is an {\em $(a, b)$-forbidding path} if the following two properties hold:
\begin{itemize}
 \item For any combination of colors $x\in L(u)$ and $y\in L(v)$, there
 exists an $L$-coloring $\gamma$ for $P$ with $\gamma(u)=x$ and
 $\gamma(v)=y$ if and only if $x\not=a$ or $y\not=b$. Such a pair $(x,y)$ is called {\em admissible} for $P$.
 \item
 For any $L$-coloring $\gamma$ of $P$ and any admissible pair $(x,y)$ with
 $x=\gamma(u)$ or $y=\gamma(v)$: there exists an $L$-recoloring sequence
 from $\gamma$ to an $L$-coloring $\delta$ with $\delta(u)=x$ and
 $\delta(v)=y$, in which every internal vertex is recolored at
 most once, and $u$ and $v$ are not recolored until the last step.
\end{itemize}
(Note that an $(a,b)$-forbidding path from $u$ to $v$ is
a $(b,a)$-forbidding path from $v$ to $u$.)
The second property implies that such an $L$-recoloring sequence has length at most $|V(P)|-1$.
For instance, a $(1,4)$-forbidding path from $u$ to $v$ with
$L(u)=\{1,2,3\}$ and $L(v)=\{2,3,4\}$ can be obtained by assigning
the following lists along a path of length 6 (starting with $L(u)$ and ending
with $L(v)$): $\{1,2,3\}$, $\{1,4\}$, $\{2,4\}$, $\{2,3\}$, $\{1,3\}$, $\{1,4\}$, $\{2,3,4\}$.
It can be verified that the two properties above hold.
In~\cite{BC09}, it was observed that for any
combination of $L(u)$, $L(v)$ and $(a,b)$ with
$L(u),L(v)\not=[4]$, an $(a,b)$-forbidding path can be constructed, of length six.
We repeat the construction here for completeness.

\begin{lem}[\cite{BC09}]
\label{lem:forbidden}
For any $L_u \subset [4]$, $L_v \subset [4]$, $a \in L_u$
and $b \in L_v$, there exists an $(a, b)$-forbidding $(u, v)$-path $P$ of length six
with $L(u) = L_u$, $L(v) = L_v$ and all other color lists $L(w) \subseteq [4]$.
\end{lem}
\PF
We can choose colors $c\in [4]\bs L_u$ and $d\in  [4]\bs L_v$.
Next, we can choose colors $e\in [4]\bs \{a,c\}$
and $f\in [4]\bs \{b,d\}$ with $e\not=f$.
Assign the following colors lists along the path:
$L_u$, $\{a,c\}$, $\{c,e\}$, $\{e,f\}$, $\{f,d\}$, $\{d,b\}$, $L_v$.
It can be verified that this path satisfies the desired properties.
\QED

The reader is referred to~\cite{BC09} for more details on the
list recoloring version of the problem and the use of $(a,b)$-forbidding paths.

\medskip

\paragraph{Construction}
Given an instance $G$ of \Pz, we construct an instance
($G'$, $L$, $\ell$, $\alpha$, $\beta$) of \LR\ as follows.
Start with the vertex set $V(G)$. All of these vertices
$u\in V(G)$ receive color $\alpha(u)=1$ and $L(u)=\{1,2,3\}$.
For every edge $uv\in E(G)$, add three vertices $x_{uv}$, $y_{uv}$ and $z_{uv}$, with
$\alpha(x_{uv})=4$,
$\alpha(y_{uv})=4$,
$\alpha(z_{uv})=4$,
$L(x_{uv})=\{1,2,4\}$,
$L(y_{uv})=\{3,4\}$, and
$L(z_{uv})=\{1,2,4\}$.
We add the following edges and paths between these vertices.

\begin{itemize}
\item
Add edges $ux_{uv}$ and $uy_{uv}$.
\item
Add a $(1,2)$-forbidding path from $u$ to $x_{uv}$.
\item
Add a $(3,1)$-forbidding path from $u$ to $x_{uv}$.
\item
Add a $(2,3)$-forbidding path from $u$ to $y_{uv}$.
\item
Add a $(2,1)$-forbidding path from $v$ to $x_{uv}$.
\item
Add a $(3,2)$-forbidding path from $v$ to $x_{uv}$.
\item
Add a $(1,3)$-forbidding path from $v$ to $y_{uv}$.
\item
Add a $(4,1)$-forbidding path from $x_{uv}$ to $z_{uv}$.
\item
Add a $(4,2)$-forbidding path from $y_{uv}$ to $z_{uv}$.
\end{itemize}
In all cases, we choose an $(a,b)$-forbidding path of length six (Lemma~\ref{lem:forbidden}).
We denote $Z=\{z_{uv} \mid uv\in E(G)\}$.
Informally, these edges and forbidding paths ensure the following property
(see Lemma~\ref{lem:x_verts_colors} below for details): whenever $u$ and $v$
have the same color, both $x_{uv}$ and $y_{uv}$ must
have color 4, and therefore $z_{uv}$ must have color 4.
On the other hand, when $u$ and $v$ currently have
different colors, then either $x_{uv}$ or $y_{uv}$ can be
recolored to a different color, and thus $z_{uv}$ can either be recolored to $1$ or $2$.

Next, we add four vertices $a,b,c,d$ to $G'$, with the following
colors and lists: $\alpha(a)=1$, $\alpha(b)=2$, $\alpha(c)=3$,
$\alpha(d)=4$, $L(a)=\{1,2,3\}$, $L(b)=\{1,2\}$, $L(c)=\{3,4\}$,
$L(d)=\{4\}$. Add all edges between these vertices, except for $cd$.
Add edges from all vertices in $Z$ to $c$. This yields the graph $G'$.
Note that for all $(a,b)$-forbidding paths that we added, we chose the
colors $\alpha$ of the end vertices $p$ and $q$ such that $\alpha(p)\not=a$
or $\alpha(q)\not=b$. So we can extend $\alpha$ to an $L$-coloring of the
entire graph (by the definition of $(a,b)$-forbidding paths); we do this in an arbitrary way.

Finally, we define the target coloring $\beta$: for all vertices
$v\in V(G')\bs \{a,b\}$, set $\beta(v)=\alpha(v)$. We set
$\beta(a)=2$ and $\beta(b)=1$, so the goal is to reverse
the colors of these two vertices, while keeping all other colors the same.

\begin{lem}
\label{lem:x_verts_colors}
Let $\gamma$ be an $L$-coloring of $G'$, and let $uv\in E(G)$. If $\gamma(u)=\gamma(v)$, then $\gamma(z_{uv})=4$.
On the other hand, if $\gamma(u)\not=\gamma(v)$, then there exists an $L$-recoloring sequence
of length at most $\Oh(1)$ from $\gamma$ to an $L$-coloring $\gamma'$ with $\gamma'(z_{uv})\not=4$ and with
$\gamma(w)=\gamma'(w)$ for all $w\in V(G)\cup Z$.
\end{lem}

\PF
We first show that if $\gamma(z_{uv})\not=4$, then $\gamma(u)\not=\gamma(v)$.
Suppose that $\gamma(z_{uv})=1$. Then the $(4,1)$-forbidding path from $x_{uv}$ to $z_{uv}$ ensures that $\gamma(x_{uv})\in \{1,2\}$.
If $\gamma(x_{uv})=1$, then the edge $ux_{uv}$ and $(3,1)$-forbidding path from $u$ ensure that $\gamma(u)\not\in \{1,3\}$, so $\gamma(u)=2$. In addition, the $(2,1)$-forbidding path from $v$ to $x_{uv}$ forces $\gamma(v)\not=2$, so in this case, $\gamma(u)\not=\gamma(v)$. Similarly, if $\gamma(x_{uv})=2$ then considering the indicent edge $ux_{uv}$ and incident forbidding paths, we conclude that $\gamma(u)=3$ and $\gamma(v)\not=3$, so again $\gamma(u)\not=\gamma(v)$.

Next, suppose that $\gamma(z_{uv})=2$. Then the $(4,2)$-forbidding path from $y_{uv}$ to $z_{uv}$ ensures that $\gamma(y_{uv})=3$. Similar to before (considering the remaining forbidding paths), this implies that $\gamma(u)=1$ and $\gamma(v)\not=1$, so $\gamma(u)\not=\gamma(v)$. We have now proved the statement in all cases. Hence if $\gamma(u)=\gamma(v)$, then $\gamma(z_{uv})=4$.

Now suppose $\gamma(u)\not=\gamma(v)$. Then considering the same color combinations and forbidding paths as above, we conclude that in every case, $x_{uv}$ can be recolored to 1 or 2, or $y_{uv}$ can be recolored to 3, possibly after first recoloring some internal vertices of incident forbidding paths, but without recoloring any other vertices. Next, $z_{uv}$ can be recolored to 1 or 2, again after possibly recoloring some internal vertices of the incident forbidding paths. This shows that $z_{uv}$ can be recolored to a color different from 4 in $\Oh(1)$ recoloring steps, without changing the color of any other vertex in $V(G)\cup Z$.
\QED

\begin{lem}
\label{lem:3col_recol}
If $G$ is 3-colorable, then there exists an $L$-recoloring
sequence for $G'$ from $\alpha$ to $\beta$, of length $\Oh(m)$, where $m=|E(G)|$.
\end{lem}

\PF
The vertices of $G$ form an independent set in $G'$. Therefore, if $G$ is 3-colorable we
can start by recoloring the corresponding vertices in $G'$ to such a 3-coloring, using the colors $1,2,3$.
Since all of the $(a,b)$-forbidding paths in $G'$ from a vertex $u\in V(G)$
to another vertex $v$ satisfy $\alpha(v)\not=b$ and $v\not\in V(G)$, it follows
from the definition that this can be done while recoloring all vertices from
$V(G)$ and all internal vertices of $(a,b)$-forbidding paths at most once, and recoloring
no other vertices of $G'$. So this can be done using $\Oh(m)$ recoloring steps.

Now by Lemma~\ref{lem:x_verts_colors}, we can subsequently recolor
the vertices of these $(a,b)$-forbidding paths and all vertices in
$Z$, such that all vertices in $Z$ receive color 1 or 2. For every
vertex in $Z$, this can be done in $\Oh(1)$ recoloring steps, so
this gives $\Oh(m)$ steps in total.

Next, we can recolor $c$ to color 4.
At this point, $a$ can temporarily be recolored to 3, $b$ to $1$, and next $a$ to $2$.
Then we can reverse all previous vertex recolorings, except for $a$ and $b$, and
end up with the coloring $\beta$. The total length of this $L$-recoloring sequence is in $\Oh(m)$.
\QED

\begin{lem}
\label{lem:recol_3col}
If there exists an $L$-recoloring sequence from $\alpha$ to $\beta$ for $G'$, then $G$ is 3-colorable.
\end{lem}

\PF
By considering the vertices $a,b,c,d$, we see that any such
$L$-recoloring sequence must contain a coloring $\gamma$ with $\gamma(c)=4$.
This implies that for every $z\in Z$, $\gamma(z)\in \{1,2\}$.
Then Lemma~\ref{lem:x_verts_colors} shows that for every $uv \in E(G)$,
$\gamma(u)\not=\gamma(v)$. Hence $\gamma$ restricted to $V(G)$ is a 3-coloring of $G$.
\QED

Combining Lemmas~\ref{lem:3col_recol} and~\ref{lem:recol_3col} with the fact that we can easily
transform the \LR\ instance to an \Px\
instance (Lemma~\ref{lem:listversion}), and the NP-hardness of \Pz,
shows that \Px\ is {\em strongly} NP-hard. For this it is essential that
the parameter $\ell$ in the reduction is polynomial in the size of the \Pz-instance.
More precisely, we have the following result:

\begin{thm}
For any constant $k\ge 4$, the problem \Px, with $\ell$ encoded in unary, is NP-complete.
\end{thm}

\section{FPT algorithm}\label{sec:fpt}

For every constant $\ell$, the \Px\ problem can be solved in polynomial time, using the following simple branching algorithm. Denote the given instance by $(G, k, \ell, \alpha, \beta)$, with $|V(G)|=n$.
Start with with the intial $k$-coloring $\alpha$. For every coloring generated by the algorithm, consider all possible $k$-colorings that can be obtained from it using one recoloring step. Recurse on these choices, up to a recursion depth of at most $\ell$. Return yes if and only if in one of the recursion branches, the target coloring $\beta$ is obtained. Clearly, this algorithm yields the correct answer. For one coloring, there are at most $kn$ possible recoloring steps, so branching with depth $\ell$ shows that at most $\Oh((kn)^\ell)$ colorings will be considered. This shows that for parameter $\ell$, the problem is in XP.

Because \Px\ is NP-hard for every constant $k\ge 4$, a similar result cannot be obtained for the parameter $k$, unless $P=NP$.
Since the \Px\ problem is W[1]-hard when
parameterized by $\ell$, we also do not expect any algorithms solving the problem in $\Oh(h(\ell)(kn)^{\Oh(1)})$ time (for any computable function $h$).
However, we shall see in this section
that the problem is in fact fixed-parameter tractable
when parameterized by $k + \ell$: it can be solved in
$\Oh(f(k,\ell) n^{\Oh(1)})$ time, for some computable function $f$.

We first give a high-level description of the algorithm.
Denote $S=\{v\in V(G)\mid \alpha(v)\not=\beta(v)\}$.
Clearly, when $|S| > \ell$ we have a no-instance and when $|S| = 0$ we have a trivial yes-instance. In what follows, we assume $0 < |S| \leq \ell$.
The main challenge that we need to overcome is that the number of vertices that potentially need to be recolored cannot easily be bounded by a function of $\ell$; in particular, there may be too many vertices at distance at most $\ell$ from $S$. However, once we know which vertices will be recolored, the problem can be solved using a branching algorithm similar to the one above.

Let $R=\alpha_0,\ldots,\alpha_{\ell}$ be a recoloring sequence for a graph $G$.
For every vertex $v\in V(G)$, the {\em used-color lists} for $R$ are
defined as $U(v)=\{\alpha_i(v) \mid i\in\{0,\ldots,\ell\}\}$. Note that
a vertex $v$ is recolored at least once in $R$ if and only if $|U(v)|\ge 2$.
In addition we have the following simple but useful observation.

\begin{propo}
\label{propo:limited_options}
Let $R$ be a recoloring sequence for $G$ of length $\ell$, and let $U$ denote
the used-color lists for $R$. Then $\sum_{v\in V(G)} (|U(v)|-1)\le \ell$.
\end{propo}

Our main algorithm to solve the \Px\ problem is Algorithm~\ref{alg:main}, which
uses the subroutine given in Algorithm~\ref{alg:listrecolor}.
The \textsc{Recolor} algorithm (Algorithm~\ref{alg:main}) consists of a two-stage branching algorithm.
The first stage of the algorithm ignores the ordering of recoloring steps and simply tries to ``guess'' the used-color lists for each vertex, assuming that a recoloring sequence $R$ from $\alpha$ to $\beta$ of length at most $\ell$ exists.
These guesses are stored in the lists $L(v)$.
Clearly, $\{\alpha(v),\beta(v)\}\subseteq L(v)$ should hold.
To construct these lists $L$, the algorithm maintains two disjoint sets of vertices $A$ and $B$ as follows.
All vertices in $A\cup B$ will be recolored at least once, according to our current guess. Vertices are in $B$ if we have already guessed a used-color list for them.
Initially, we have $A = S$ and $B = \emptyset$.
While $A$ is not empty, we pick a vertex $v \in A$ and branch on
all possible lists $L(v)$.
We then delete $v$ from $A$ and add it to $B$.
Before continuing with the next vertex from $A$,
we inspect the neighbors of $v$. If there exists $u \in N_G(v)\bs (A\cup B)$ such
that $\alpha(u) \in L(v)$, we add $u$ to $A$ since $u$ must also be
recolored at least once, assuming that $v$ will indeed receive all colors in $L(v)$.

If we reach a state where $\sum_{v \in B} (|L(v)| - 1) > \ell$, then
the current branch is ignored since these lists cannot correspond to used-color lists of a recoloring sequence of length at most $\ell$.
On the other hand, when $A = \emptyset$ and $\sum_{v \in B} (|L(v)| - 1) \leq \ell$,
we have a ``possible solution''.
That is, we still need to make sure that there
exists a feasible ordering of the recoloring steps that transforms $\alpha$ to $\beta$.
This is handled by the \textsc{ListRecolor} subroutine (Algorithm~\ref{alg:listrecolor}), which is a branching algorithm similar to one sketched in the beginning of this section, although we only assign colors from the lists $L(v)$. Since $\sum_{v \in B} (|L(v)| - 1) \leq \ell$, at any time there are at most $\ell$ different ways to recolor a vertex, according to the lists. So, branching up to a depth of $\ell$, this yields an FPT algorithm for (such instances of) the \LR\ problem, parameterized by $\ell$. Combined with Algorithm~\ref{alg:main}, which generates all relevant guesses for the used-color lists, this yields an FPT algorithm for the \Px\ problem, parameterized by $k+\ell$. We now present the details of these algorithms, starting with the \textsc{ListRecolor} subroutine (Algorithm~\ref{alg:listrecolor}).

\begin{algorithm}
\caption{{\ListRecolor$(G,L,\alpha,\beta,\ell)$}}
\label{alg:listrecolor}
\begin{ntabbing}
\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill

{\bf Input:} A graph $G$, nonnegative integer $\ell$, color lists $L(v)$
for all $v\in V(G)$,\\ and two $L$-colorings $\alpha$ and $\beta$ of $G$.\\
{\bf Output:} ``YES'' if and only if there exists an $L$-recoloring sequence \\
from $\alpha$ to $\beta$ of length at most $\ell$.\\
\\
Return \Recurse$(\alpha,\ell)$\label{la:list1}\\
\\
Subroutine \Recurse$(\gamma,\ell')$:\\
\\
if $\gamma=\beta$ and $\ell'\ge 0$ then return YES\label{la:list2}\\
if $\ell'\le 0$ then return NO\label{la:list3}\\
for all
$L$-colorings $\delta$ that can be obtained from $\gamma$ by changing the\label{la:list4}\\
\> \> color of a single vertex $x$ to a different color in $L(x)$:\\
\> if \Recurse$(\delta,\ell'-1)$=YES then return YES\label{la:listcsp5}\\
return NO\label{la:listcsp6}
\end{ntabbing}
\end{algorithm}

\begin{lem}
\label{lem:listRecol}
Let $(G,L,\alpha,\beta,\ell)$ be an input for Algorithm~\ref{alg:listrecolor}, with $n=|V(G)|$, and let $p=\sum_{x\in V(G)} (|L(x)|-1)$.
In time $\Oh(p^\ell \cdot \poly(n))$, Algorithm~\ref{alg:listrecolor} decides whether there exists an $L$-recoloring sequence for $G$ from $\alpha$ to $\beta$, of length at most $\ell$.
\end{lem}
\PF
An easy induction proof shows that a recursive call \Recurse$(\gamma,\ell')$ in Algorithm~\ref{alg:listrecolor} returns YES if and only if there exists an $L$-recoloring sequence from $\gamma$ to $\beta$ of length at most $\ell'$: Line~\ref{la:list4} guarantees that every new $\delta$ that is generated is again an $L$-coloring, which is adjacent to $\gamma$ in $\CC(G,L)$. This shows that the algorithm is correct.

For every $L$-coloring $\gamma$, there are $p$ ways to change the color of some vertex $x\in V(G)$ to a different color in $L(x)$. So at most $p$ new $L$-colorings are generated in one recursive call. Obviously, the recursion depth is at most $\ell$, so this shows that at most $\Oh(p^\ell)$ recursive calls are made in total. One recursive call takes time $\poly(n)$, so this yields the stated complexity bound.
\QED

\begin{algorithm}
\caption{{\sc Recolor$(G,k,\ell,\alpha,\beta)$}}
\label{alg:main}

\begin{ntabbing}
\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\qquad\=\kill

{\bf Input:}
A graph $G$, nonnegative integers $k$ and $\ell$, and \\
two $k$-colorings $\alpha$ and $\beta$.\\

{\bf Output:} ``YES'' if and only if there exists a $k$-recoloring sequence \\
from $\alpha$ to $\beta$ of length at most $\ell$.\\
\\

$S:=\{v\in V(G) \mid \alpha(v)\not=\beta(v)\}$\label{la:1}\\
if $|S|>\ell$ then return ``NO''\label{la:2}\\
if $|S|=0$ then return ``YES''\label{la:3}\\
Return \Recurse$(S,\emptyset,\{\emptyfunc\})$\label{la:5}\\
\\
Subroutine \Recurse$(A,B,L)$:\\
\\
if $\sum_{v\in B} (|L(v)|-1)>\ell$ then return ``NO''\label{la:6}\\
if $A=\emptyset$ then return \ListRecolor$(G[B],L,\alpha\restr_B,\beta\restr_B)$\label{la:7}\\
Choose $v\in A$.\label{la:8}\\
$B':=B\cup \{v\}$\label{la:9}\\
for each $U\subseteq [k]$ with $2\le |U|\le \ell$ and $\{\alpha(v),\beta(v)\}\subseteq U$:\label{la:11}\\
\> $L'(v):=U$\label{la:12}\\
\> for each $u\in B$:\label{la:13}\\
\> \> $L'(u):=L(u)$\label{la:14}\\
\> $A':=A\bs \{v\}$\label{la:15}\\
\> for each $u\in N(v)\bs (A\cup B)$ with $\alpha(u)\in U$:\label{la:16}\\
\> \> $A':=A'\cup \{u\}$\label{la:17}\\
\> if \Recurse$(A',B',L')$=``YES'' then return ``YES''\label{la:18}\\
return ``NO''\label{la:19}
\end{ntabbing}
\end{algorithm}

\begin{lem}
\label{lem:invariant}
Let $\alpha$ and $\beta$ be two $k$-colorings for a graph $G$, and $\ell\in \mathbb{N}$.
For every recursive call \Recurse$(A,B,L)$ made by Algorithm~\ref{alg:main} on this input, the following conditions hold:
\begin{enumerate}[(1)]
 \item\label{it:one} $A$ and $B$ are disjoint subsets of $V(G)$.
 \item\label{it:two} For every $u\in V(G)\bs B$: $u\in A$ if and only if
   \begin{enumerate}[(a)]
   \item\label{it:a} $\alpha(u)\not=\beta(u)$, or
   \item\label{it:b} there exists an edge $uv\in E(G)$ with $v\in B$ and $\alpha(u)\in L(v)$.
   \end{enumerate}
\end{enumerate}
\end{lem}

\PF
The first time the subroutine \Recurse\ is called (in Line~\ref{la:5}),
$B=\emptyset$, and $A$ contains exactly those vertices
that have different colors in $\alpha$ and $\beta$, so clearly the above conditions are satisfied.

Now consider a call \Recurse$(A,B,L)$ where the arguments satisfy the given
conditions, and an iteration of the for-loop in Line~\ref{la:11} where a
subsequent call \Recurse$(A',B',L')$ is made. Lines~\ref{la:9},~\ref{la:15} and~\ref{la:17}
show that $A'$ and $B'$ are again disjoint (in Line~\ref{la:17}, only vertices
outside of $B'$ are added), so Condition~(\ref{it:one}) is again satisfied.
For vertices in $A\bs \{v\}$, it still holds that at least one of the
Conditions~(\ref{it:a}) and~(\ref{it:b}) is satisfied (also with respect
to the new lists $L'$). Lines~\ref{la:16} and~\ref{la:17} show that
the newly added vertices in $A'$  are exactly those that now satisfy
Condition~(\ref{it:b}), since $L'(v)=U$ and $v$ is the only new vertex in $B'$.
We conclude that both Conditions~(\ref{it:one}) and~(\ref{it:two}) are maintained for $A',B',L'$.
By induction, it follows that for every recursive call
\Recurse$(A,B,L)$, the above conditions hold for $A$, $B$ and $L$.
\QED

\begin{lem}
\label{lem:main_alg_correct_easy}
Let $\alpha$ and $\beta$ be two $k$-colorings for a graph $G$, and $\ell\in \mathbb{N}$.
If Algorithm~\ref{alg:main} returns ``YES'' then there exists a
$k$-recoloring sequence for $G$ from $\alpha$ to $\beta$ of length at most $\ell$.
\end{lem}

\PF
Consider a recursive call \Recurse$(A,B,L)$.
If ``YES'' is returned in Line~\ref{la:7}, then $A=\emptyset$, and there exists an $L$-recoloring sequence for $G[B]$ from $\alpha\restr_B$ to $\beta\restr_B$ of
length at most $\ell$.
Since $A=\emptyset$, this also yields a valid recoloring sequence for the entire graph $G$,
starting from $\alpha$, of the same length. This is because any color
that is assigned to a vertex $v\in B$ is chosen from $L(v)\subseteq [k]$, and therefore does not conflict with the color $\alpha(w)$ of any vertex
$w\in V(G)\bs B$ (by Condition~(\ref{it:b}) from Lemma~\ref{lem:invariant}).
In addition, Condition~(\ref{it:a}) shows that the recoloring
sequence that we obtain for $G$ this way ends with $\beta$.
We conclude that there exists a $k$-recoloring sequence from $\alpha$ to $\beta$ for $G$, of length at most $\ell$.
If YES is returned by a subsequent recursive call in Line~\ref{la:18}, then the claim follows by induction.
\QED

\begin{lem}
\label{lem:main_alg_correct_hard}
Let $\alpha$ and $\beta$ be two $k$-colorings for a graph $G$, and $\ell\in \mathbb{N}$.
If there exists a
$k$-recoloring sequence for $G$ from $\alpha$ to $\beta$ of length at most $\ell$
then Algorithm~\ref{alg:main} returns ``YES''.
\end{lem}

\PF
We prove by induction that for every call \Recurse$(A,B,L)$, ``YES'' is returned if
\begin{enumerate}[(1)]
 \setcounter{enumi}{2}
 \item\label{it:three} there exists a $k$-recoloring sequence $R$ from $\alpha$
 to $\beta$ for $G$, of length at most $\ell$, such that for
 every vertex $v\in B$, $L(v)$ is (exactly) the set of colors used by $R$ for $v$.
\end{enumerate}
Applying this statement to the initial call \Recurse$(S,\emptyset,\{\emptyfunc\})$ in Line~\ref{la:5} proves the lemma.

Suppose Condition~(\ref{it:three})
is satisfied for $A,B,L$. We show that ``YES'' is returned.
Let $R$ be a corresponding recoloring sequence from
$\alpha$ to $\beta$, of length at most $\ell$, which uses
exactly the colors $L(v)$ for each $v\in B$.
First, Proposition~\ref{propo:limited_options} shows
that ``NO'' is not returned in Line~\ref{la:6}, and the algorithm continues.
If there are no vertices $u\in V(G)\bs B$ that satisfy
Condition~(\ref{it:a}) or~(\ref{it:b}), then $A=\emptyset$
(Lemma~\ref{lem:invariant}), so a call to \ListRecolor\ is made in Line~\ref{la:7}.
Restricting all colorings in $R$ to $B$ yields a $k$-recoloring
sequence for $G[B]$ from $\alpha\restr_B$ to $\beta\restr_B$ that
uses exactly the colors in $L$ for each vertex, of length at
most $\ell$, so in this case, ``YES'' is returned.

In the remaining case, we may assume that $A$ is nonempty, and
a vertex $v\in A$ is chosen in Line~\ref{la:8}. Let $U$ be
the set of colors used for $v$ by the sequence $R$.
So $\{\alpha(v),\beta(v)\}\subseteq U$. In addition, we argue
that $|U(v)|\ge 2$. If $\alpha(v)\not=\beta(v)$, this is obvious.
Otherwise, by Condition~(\ref{it:two}) from Lemma~\ref{lem:invariant}, $v$ has
a neighbor $u\in B$ with $\alpha(v)\in L(u)$. Since $R$ uses
exactly the colors $L(u)$ for $u$, $v$ must be recolored at least once, and thus $|U|\ge 2$.
We conclude that $U$ will be considered in an iteration of the for-loop in Line~\ref{la:11}.
Let $L', A', B'$ be the lists and sets as constructed in this iteration.
We observe that $R$ again satisfies the properties from
Condition~(\ref{it:three}), also with respect to this $L'$ and $B'$.
Indeed, $B'=B\cup \{v\}$, and $L'(v)=U$, which is exactly the set of
colors used by $R$ for $v$. For all other vertices $w\in B'$, $L(w)=L'(w)$.
So we may use induction to conclude that ``YES'' is returned by the
call \Recurse$(A',B',L')$, and thus in Line~\ref{la:18}, ``YES'' is returned.
\QED

\begin{lem}
\label{lem:main_alg_runtime}
The \textsc{Recolor} algorithm (Algorithm~\ref{alg:main}) runs in $\Oh(2^{k(\ell+1)}\cdot \ell^\ell\cdot \poly(n))$ time, where $n=|V(G)|$.
\end{lem}

\PF
The search-tree produced by the \textsc{Recolor} algorithm
has depth at most $\ell+1$, since every branch increases the quantity
$\sum_{v\in B} (|L(v)|-1)$ by at least $1$ (Line~\ref{la:11}) and the base case is reached whenever $\sum_{v\in B} (|L(v)|-1) > \ell$ (Line~\ref{la:6}).
The number of sets considered in the for-loop in Line~\ref{la:11} is at most $2^k$, so every node in the search-tree has at most $2^k$ children. We conclude that at most $\Oh(2^{k(\ell+1)})$ recursive calls are made in total.

We now argue that for every recursive call, we spend at most $\Oh(\ell^\ell \cdot \poly(n))$ time in total. For Line~\ref{la:7}, this follows from Lemma~\ref{lem:listRecol}, noting that whenever this line is reached, $p=\sum_{v\in B} (|L(v)|-1)\le \ell$ holds (Line~\ref{la:6}). All other lines can easily be implemented to run in time $\poly(n)$. (Note that we may assume w.l.o.g.\ that $k\le n+1$.) We attribute the time spent in Lines~\ref{la:12}--\ref{la:18} to the resulting recursive call in Line~\ref{la:18}.
This shows that the entire complexity can be bounded by $\Oh(2^{k(\ell+1)}\cdot \ell^\ell\cdot \poly(n))$.\QED

Combining Lemmas~\ref{lem:main_alg_correct_easy},~\ref{lem:main_alg_correct_hard} and~\ref{lem:main_alg_runtime}
yields the main result of this section:

\begin{thm}
$\ell$-Length $k$-Color Path is fixed-parameter tractable when parameterized by $k + \ell$.
\end{thm}

\bibliographystyle{plain}

redpajama_set_name: RedPajamaArXiv


text:
Home Cybersecurity
TCP Flaw No Cause for Alarm
While word of a major vulnerability in the fabric of the Internet leaked out a bit sooner than folks at the Department of Homeland Security would have liked, there isnt a whole lot to panic about.
The threat posed by an exploit of the TCP has already been addressed where it matters most—at the core of the Internet. Unless youre heavily using the BGP (Border Gateway Protocol) to manage routing of your network traffic to ISPs, odds are that youre not at risk.
The potential problem only applies to applications that rely on having a long-term TCP session between two points. But few applications use TCP for such applications—streaming video and audio, for example, typically rely on the UDP (User Datagram Protocol) instead.
Unfortunately, one place where such long-term TCP sessions are common is communication between routers over BGP. The greatest vulnerability is at "peer border routers"—the routers at the edge of an ISPs network that link pairs of ISPs together.
"If BGP peers get knocked off, it can take some time to rebuild those connections," says Peter Stapleton, director of product marketing for Computer Associates International Inc.
By sending a "spoofed," or faked, TCP message, an attacker could reset the TCP session between two border routers; that would reset the BGP session between them as well, and any routing information built between the routers would have to be rebuilt. If carried out repeatedly, the attack could stop traffic between two ISPs by way of that peer connection.
/zimages/4/28571.gifFor insights on security coverage around the Web, check out eWEEK.com Security Center Editor Larry Seltzers Weblog.
Fortunately, most ISPs have already taken steps to secure the traffic between their peer border routers. "Its something weve known about in the operations community for over a week now," says Bill Woodcock, research director of the Packet Clearing House, a nonprofit organization that promotes Internet stability by working with ISPs.
In that time, ISPs have been working with each other to secure each of their peer links "using an MD5 (Message Digest 5) Hash to protect each session," says Woodcock, "putting a unique password on every interconnection between each pair of ISPs."
The MD5 algorithm, designed by Ron Rivest in 1991, has been available for some time; it was defined as an optional extension to BGP in the Internet Engineering Task Forces RFC 2358 back in 1998. "Its been around for a while," says Stapleton, "but as far as being a common practice, thats another matter. Up until now, it hasnt been used that much."
That has changed in the last week. "All of the big guys got this done days ago," says Woodcock. "Its come down to the last couple of small guys who are harder to pay attention—the vulnerability will only affect smaller ISPs that are less concerned about security."
/zimages/4/28571.gifCheck out eWEEK.coms Security Center at http://security.eweek.com for security news, views and analysis.
Be sure to add our eWEEK.com security news feed to your RSS newsreader or My Yahoo page: http://us.i1.yimg.com/us.yimg.com/i/us/my/addtomyyahoo2.gif
Sean Gallagher is editor of Ziff Davis Internet's enterprise verticals group. Previously, Gallagher was technology editor for Baseline, before joining Ziff Davis, he was editorial director of Fawcette Technical Publications' enterprise developer publications group, and the Labs managing editor of CMP's InformationWeek. A former naval officer and former systems integrator, Gallagher lives and works in Baltimore, Maryland.


text:
Johnny Walker's late goal lifts No. 15 ASU hockey to tie with No. 3 Minnesota State
Johnny Walker scored with 29 seconds remaining Saturday night, giving No. 15 Arizona State hockey a 2-2 tie with No. 3 Minnesota State.
Johnny Walker's late goal lifts No. 15 ASU hockey to tie with No. 3 Minnesota State Johnny Walker scored with 29 seconds remaining Saturday night, giving No. 15 Arizona State hockey a 2-2 tie with No. 3 Minnesota State. Check out this story on azcentral.com: https://www.azcentral.com/story/sports/college/asu/2018/12/29/asu-hockey-johnny-walkers-late-goal-leads-tie-minnesota-state/2443574002/
Arizona State University's Demetrios Koumontzis (23) battles for the puck against Clarkson's Jordan Schneider (12) during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Desert Hockey Classic
Arizona State University goalie Joey Daccord (35) saves the puck against Clarkson's Nico Sturm (17) during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Jordan Sandhu (19) fights for the puck with Clarkson's Jere Astren (20) during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Dylan Hollman (12) goes for the puck against Clarkson's Michael Underwood (5) during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University goalie Joey Daccord (35) deflects the puck against Clarkson during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University players huddle around the goal before their match against Clarkson in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Johnny Walker (7) just misses getting a shot off Clarkson's goalie Jake Kielly (28) during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Johnny Walker (7) controls the puck while trying to set up a power play against Clarkson's defense during the second period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Johnny Walker (7) is out numbered around the Clarkson goal during the second period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Max Balinson (26) controls the puck against Clarkson's Jack Jacome (16) during the second period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Demetrios Koumontzis (23) loses the puck against Clarkson's Aaron Thow(13) during the second period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Brinson Pasichnuk (39) controls the puck against Clarkson's Jordan Schneider (12) during the second period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. Darryl Webb/Special for the Republic
Arizona State University's Demetrios Koumontzis (23) battles for the puck against Clarkson's Jordan Schneider (12) during the first period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018.
Jeff Metcalfe, Arizona Republic Published 11:14 p.m. MT Dec. 29, 2018
Arizona State University's Johnny Walker (7) controls the puck while trying to set up a power play against Clarkson's defense during the second period of their game in the 2018 Desert Hockey Classic in Glendale, Friday, Dec. 28, 2018. (Photo: Darryl Webb/Special for the Republic)
ASU (14-7-1) also won a shootout following overtime 1-0 in a game that counts as a tie. Max Balinson scored in the fifth round of the shootout.
The Sun Devils rebounded from a 3-0 loss to No. 19 Clarkson on Friday in the Desert Hockey Classic at Gila River Arena.
ASU led 1-0 after the first period on a goal by Jordan Sandhu. Minnesota State (14-5-1) scored twice in the second period before Walker got the equalizer in the final minute with ASU goalie Joey Daccord off the ice.
The Sun Devils are at home again against Boston College (6-6-2) on Friday at Oceanside Ice Arena and Jan. 5 at Gila River Arena.
In the first game Saturday, Clarkson won 3-1 over No. 4 Minnesota Duluth to take the tournament title.
Shane Kuzmeski and Nico Sturm scored in the first period for Clarkson (11-6) then Strum added an empty-net goal late in the third for the clincher.
Defending NCAA champion Duluth, which won 4-3 over Minnesota State on Friday, dropped to 11-5-2. The Bulldogs had a 30-15 shots advantage vs. Clarkson but their only goal came early in the second period by Parker Mackay.
Clarkson flexes power-play muscle in win over ASU hockey
ASU hockey making huge strides under coach Greg Powers in 2018-19 season
Short of perfection: Rattlers suffer first loss to Sioux Falls in United Bowl
Merrill Kelly's miscues help Cardinals down Diamondbacks
'Crazy' Rattlers fan hopes to add perfect season to his tattoo with United Bowl win
Suns' summer upheaval wasn't splashy, but was constructive
Should the Diamondbacks buy or sell at trade deadline? Why not both?
Diamondbacks down Goldschmidt, Cardinals in first game after All-Star break


A space within a space: The design enriches a relatively small gallery providing an intimate reception area for prospective purchasers alongside a carefully climatically controlled storage facility. The concept came about through a collaboration between studio 24 Architects, AS Workshop and students from the University of Westminster, in response to a brief for a storage facility and gallery prospect on behalf of Faggionato Fine Art based in the London borough of Westminster.
The design reflects the expectations and heightened perceptions of a prospective client or art collector to an exhibition space away from the main gallery. The design intent was to employ architectural concepts to make social interaction a dynamic experience, whilst utilising the least possible amount of building fabric. Clients pass through a sequential interconnected set of spaces via pivoting large doors that provide both security, privacy and separation between rooms. The calm aesthetic employs reflective and rich natural materials set against a white backdrop to emphasise space and light with the main focus of colour represented via the visible artwork. Upon leaving the interested works, clients pass into an aesthetically articulated meeting space, elevated by a triangular faceted wooden soffit, with washrooms, a reference library and refreshments situated adjacent.
The environmental conditions required to maintain fine art are usually mechanically controlled, to keep temperature and humidity within tight limits. The consequence is that such schemes have a high carbon footprint, resulting both from the embedded energy in elaborate and expensive plant which requires regular maintenance and replacement, and high energy use to run the plant. Here the reliance on an active HVAC system has been removed through the application of materials with a low natural inertia to balance climatic conditions. The concept demonstrates the potential to achieve environmentally stable conditions within a low tech and low cost intervention that also enhances the visitor experience.


text:
Category Archives: Schools
Posted on February 15, 2012 | Leave a comment
An era came to an end in Bradley last week. Assuming that the construction of the new gym is completed as planned, the evening of Tuesday, February 7, 2012, saw the last regularly scheduled home game in the 1962 gymnasium, with the Bradley Senior Boys defeating the Horatio Senior Boys.
The first game in the 1962 gym was played in the fall of that year, with the Bright Star Junior Boys defeating the Bradley Junior Boys, 26–22.
Below are some photos taken during and immediately after the final home game last week.
For the benefit of those who may not be close enough to Bradley to see the progress on the new gym, here are two photos which may give some perspective on that progress.
The first photo was taken on June 12, 2011:
And the photo below, taken on January 29, 2012, from approximately the same angle, shows the completed slab of the building:
Posted in Buildings, Photos--current, Schools, Sports
First Grade Class, 1937 (Updated)
Below is a photo of Miss Raye Crabtree's first grade class in 1937, standing in front of what was then the relatively new gymnasium. The photo is courtesy of Gayle Garner, who is the boy in the middle of the front row. If any reader can identify any of the other class members, both bradleyark.com and Gayle would appreciate it.
UPDATED 11/10/10: Mrs. Ida Mae Black Dillard, who was a member of this class, has graciously furnished bradleyark.com with a list identifying most of the members of this class, and has also furnished another photo of the same class as fourth graders in 1940!
In the photo above, the first graders are:
Front row, L-R: Sadie May Tompkins, Jane Riley, Martha Jean Baker, Ida Mae Black, James Gayle Garner, Glayes Burns, Paulene Burns, _____ Benefield, William Adams.
Middle row, L-R: James Thomas Benefield, Ann Barker, Glen Newton, Earlene Tucker, ____________, Nettie Baker, Lucy Short, Georgie Philips, Doris Jean Daniels.
Back row, L-R: ____________, Clovis Harvin, Margret Beason, Ethel Lambeth, Odessa Stanley, Charles Haley, Opel Powell, Lola Brown, Chester Cross.
And below is the 1940 photo of the same class as fourth graders:
Front row, L-R: Ida Mae Black, James Gayle Garner, Gordon Lewis Jones, J. B. Hartsfield, Opel Smith, Jane Holland, Netty Baker, Lucille Arnold, Alice Moore, Susie Weems, Martha Jean Baker, Doris Jean Daniels.
Middle row, L-R: Carol _______, Andrew Whisenhunt, Dan Howard, Ann Barker, Betty Jo Henderson, Margret Young, Glades Burns, Austen Templeton, Lucy Short, Charles Haley, Haward Hodges, Opel Powell.
Back Row, L-R: Carl Adams, Dorothy Black, Ethel Lambeth, Rosemary Brown, Odessa Stanley, James Elbert Newton, Earlene Tucker, Charlene Welborn, Clovis Harvin, Geneva Sandlin, _____________.
Standing in back is William Church. The teacher is Miss Christene Smith.
Bradleyark.com wishes to thank Mrs. Ida Mae Black Dillard for sharing these photos and this information.
Posted in Photos--old, Schools
Bradley High School Class of 1970 40th Anniversary Reunion
This past Saturday, June 12, 2010, the Bradley High School Class of 1970 gathered for a class reunion on the 40th anniversary of their graduation. Below is a photo of those present.
Faces in the above photo are obviously difficult to discern, so here are two zoomed-in photos of the participants. Somehow Jerry Pickett and Odis Weems, the two gentlemen at the right of the group photo above, got left out of the close-up photos below.
Shown in the above photo are, left to right: Rodney Burton, Bobby Brackman, Velinda Potts Hanson, Nancy Adkins Kees (in rear), Margaret Spence Cannon, Charanda Pratt Pool, and Carl Stephens.
Shown in the above photo are, left to right: Carl Stephens, David Thompson, Gary Burton, Marion Cochran Morgan, Carl Wayne Adams, Kay Baker Weems, Janis Stone Kirwin (partially obscured in rear), and Glenda Allen Ray.
Posted in Photos--current, Schools
Bradley High School Ultimate Reunion, March 27, 2010 (Part 2 of 2)
As mentioned in the last post, approximately 200 people attended the B. H. S. Ultimate Reunion. Some left before their class had its picture taken and some classes never assembled for pictures at all. The four classes who did have their pictures taken were the classes of 1960, 1963, 1964, 1965.
Below are each of those four classes, shown first as a group, and then with either two or three closer-up photos. While I know the names of most of the people in the photos, there are a few whom I cannot presently identify. Married names of the ladies present posed another problem. A blank space in the captions below indicates that I cannot identify a particular person, or that lady's married name. Any help that readers can provide by leaving a comment as to correct identity or correct spelling of name(s) would be greatly appreciated.
As mentioned in previous posts, each caption refers to the photo or photos under that caption.
The class of 1960 is observing the 50th anniversary of its graduation this year. Sixteen of the 20 living graduates attended the reunion. Two others are deceased. Below are, left-to-right: Jerry Wilson, Jay Cheney, Mary Harrist Crabtree, Gene Smith, Melba Cox Cheney, Carroll Nations, Judie Williams Carey, Marie Russ, Jerrell Caskey, Charles Lane, Jimmy Thompson, Della Keith ________.
Shown below are some members of the class of 1963. Left-to-right: Pat Givens Calhoun, Eddie Adkins Stout, John Dinkins, Donna Vickers Jackson, Buck Williams, Diane Higdon Fletcher, Marvin Cross, Betty Weems Bourg, Doris Taylor Caswell, Joyce Dinkins Caskey.
Shown below are some members of the class of 1964. Seated, left-to-right: Ronnie Odom, Averial Redmon. Standing, left-to-right: Jimmy Gildon, Carl Pauley, Ronald Jim Byrd, Jerry Clary, Dickie Bishop, Patsy Collier Vines, Henry Maness, Johnny Umphries.
Shown below are some members of the class of 1965. Left-to-right: Bill Lee, Linda Nolte Umphries, Wayne Sparks, Linda Kay Bussey Pickler, Margie Duke Odom, Jerry Dyer, Cheryl Cason Taylor, Mitchie Jones (mostly obscured), Charlotte Hinds Brumley, Bruce Lee.
Let's do this again sometime!
Posted in Gov. Conway Days, Photos--current, Schools
An added feature during the Governor Conway Days celebration this year was the Bradley High School Ultimate Reunion, which took place in the fellowship hall of the Bradley Baptist Church beginning at 3:00 P. M. on Saturday, March 27, 2010. The reunion featured all the classes from 1960 to 1970 and was attended by approximately 200 people. Each of the classes had a table set up for it, some with memorabilia and old photos.
Below are some of the photos taken that afternoon. As with previous posts, the caption refers to the photo under the caption.
The Givens brothers, Bill (William) and Oscar, both class of 1967.
The Adkins sisters, Nancy Adkins Kees ('70) and Eddie Adkins Stout ('63).
Glenda Knott Givens ('69), David Byrd ('67), and LaDonna Collier McLain ('67).
Mary Harrist Crabtree ('60) and Marie Russ ('60).
Sister and brother Betty Jackson Cook ('66) and Buddy Ray Jackson ('65).
James Drake ('62) and Gene Smith ('60).
Linda Kay Bussey Pickler ('65) and Patsy Collier Vines ('64).
Marvin Cross ('63) and John Dinkins ('63).
Former Bradley High School faculty member Don McLaurin and his wife, Marion.
Earl Vickers ('69) and Billy Bynum ('69).
Cheryl Cason Taylor ('65) and Patsy Collier Vines ('64).
Susie Cochran Hargis ('69), John Bishop ('69), Vickie Powell Paige ('69), Clyde Stephens ('62) and Dolores Maness Grimes ('69).
Next: Group photos of some of the members of the classes of 1960, 1963, 1964, and 1965 who attended the reunion.
Dedication of Travis S. Gore Park, 3-8-10
This past Monday afternoon, March 8, 2010, approximately a hundred people gathered at the Bradley High School building for a brief ceremony dedicating the school baseball and softball fields as "Travis S. Gore Park."
For readers who have not been to Bradley in the last few years, the baseball field remains where it has been located since at least 1950. The softball field is located in the north portion of what was once the football field, with home plate near what would have been the northeast corner of the north end zone of the football field.
Current Bradley Schools Superintendent Gammye Moore, in the purple jacket, below, began the ceremony by announcing its purpose and identifying the honoree, who, notwithstanding the presence of many members of his family, demurred that he was under the impression that he was coming to a ceremony honoring Bradley's current basketball coach, Bennie Harris.
Those making brief remarks included former Bradley School Board President Andrew Whisenhunt, current basketball coach Bennie Harris, former Bradley Elementary School Principal John K. "Buddy" Black, former (early 1950's)basketball coach Joe Langdon, Mollye McCalman, and former faculty member Richard Johnson.
Coach Bennie Harris, below, with Travis, told a humorous story of how he once was working as a law enforcement officer and realized that there was a vehicle behind him, following his every move. Thinking this rather unusual, he stopped his patrol unit and the vehicle behind him also stopped. It turned out to be Travis Gore, wanting to hire him as Bradley's basketball coach.
Travis was presented with a plaque, which he is holding in the photo below.
Below, left to right, are Coach Bennie Harris, John K. "Buddy" Black, and Travis Gore.
Below, left to right, are Coach Joe Langdon, Travis Gore, and Andrew Whisenhunt. Coach Langdon was Travis' coach when Travis was in Bradley High School.
Before refreshments were served, the ceremony adjourned to the newly-erected gate on the road going into the baseball and softball fields from Highway 160. Travis and many members of his family gathered for a picture below the gate.
For the curious, "S." is for Sherman.
Posted in People, Photos--current, Schools
Class of 1959 Reunion, May 16, 2009
Last year, the Bradley High School class of 1959 assembled for its 50th reunion. Thanks to LaVerne Keahey for the following article and photo.
"The Bradley Bears Class of '59 returned to their High School den recently for their Fiftieth Reunion. Eighteen of their class of twenty-seven and one faculty member were reunited at the Bradley Baptist Church Family Life Center on May 16, 2009, for an afternoon of activities and a Fish Fry prepared on site. A slide show from pictures submitted by classmates covering the last fifty years helped share stories of families, careers, homes, pets and hobbies. Four members were memorialized. Several gag awards added fun to the event, which was highlighted by the female classmates naming "The Best Looking Old Man." The warm greeting and hugs paid tribute to Bradley High and to the closeness they had treasured as a class.
The room was decorated in a purple and gold reunion theme with sand buckets holding a branch with classmates' names on Bear cutouts on each table. The snack table held a Teddy Bear fishing in a goldfish bowl. An eight-by-ten picture of each classmate was presented with their picture, classmate names on a bookmark, a magnet showing all the buildings in which they had been schooled, and a directory of classmates from Arkansas, Louisiana, Texas, Oklahoma, Tennessee, and Mississippi as mementos.
Seated, L-R: Cheroyl Owens Taylor, Ann Copeland Dickson, Wanda Spruell Hays, Nellie Givens Nichols, Carolyn Kilgore Lamar, and Kathleen Spruell Malone.
Standing, L-R: Bette Barnett Davis, Ralph Hamner, Martha Williams Mueller, Cecil Smith, Linda Fay Burns Givens, B. J. Powell, Charles Ambrose, Patsy Powell Burkett, Dianne Barker Rogers, Derial Whitehead, David Umphries, and LaVerne Burks Keahey."
The four deceased members of the class are Bobby Collier, Charles Hamm, Rayford Lee and John Wynne.
The other members of the class who did not attend the reunion are Glenda Colvin Null, Gloria Pickett McCoy, Mary Wilson, Jimmy Redmon and Lawrence Shaver.
Bradley School, First Grade, 1955
On a September morning in 1955, Miss Ray Crabtree welcomed her newest first grade class. Somehow, in a feat which must have been akin to herding cats, the new students were persuaded to pose for a picture. Mrs. J. W. Camp, Sr., was there with her camera and took the photo below, which her son, Harry, has graciously provided to bradleyark.com.
Who are these kids? Even though I was a member of this class, fifty-four intervening years have drastically reduced my ability to identify them. Below are two slightly enlarged and cropped versions of the photo. Most of the identifications on these photos were made not from memory, but by comparing them with the class photos in the 1956 Bradley School yearbook. Almost certainly, there are one or more errors and, of course, some of the faces have not been labeled at all. Corrections and additional identifications will be most appreciated and promptly incorporated into the photos.
Posted in People, Photos--old, Schools
Bradley High School Class of 1962 Reunion
On June 27, 2009, the Bradley High School Class of 1962 held a reunion on the 47th [!] anniversary of its graduation. A total of 42 class members and friends attended the reunion and enjoyed catching up with each other.
James Drake, a member of that class, has provided bradleyark.com with two photos of those in attendance.
Ladies first:
Standing, left to right: Judy Cheney Bogart, Bette Whetstone Lynn, Lola Lane Starling, Faye Tucker Durabb, Sherry Jackson Hendrix, Gloria Stephens, Sharon Drake, Judy Coker and Sue Cook. Seated, left to right: Rachel McKinney, Carolyn Burks, Diane Fletcher, Mary Cross, Phyllis Barrington.
And the gentlemen in attendance:
Standing, left to right: Clyde Stephens, James Drake, Bob Coker, Dickie Bishop, Robert Lane, Samuel Marvin Cross and Willie Harrist. Seated, left to right: James Bland, Floyd Goode, Tom Burks, Henry Fletcher, Gerald Lynn and Marvin Barrington.
Thanks, James, for the photos.
This past Saturday, June 20, 2009, the Bradley High School Class of 1969 came together for a class reunion on the 40th anniversary of their graduation. Below is a photo of those present, with the exception of one person who arrived after the photo was taken.
From left to right: Johnny Craig, Danny Maness, Ricky Powell, Dennis McEachern, Jan Allen Segrest, Curtis Thompson, Betty Carol Endsley Stanley, Penny Dreher Lyons, Delores Maness Grimes, Linda Goodwin Elledge, Barbara Price McGuffie, Carroll Collier (partially obscured), Jean Starling Burnett, John Bishop, Billy Bynum, Vicky Powell Paige, Bobby Works, Buddy Stevenson, Earl Vickers, Susie Cochran Hargis, Jimmy Ray Dickerson, Peggy Wilson Cook, and Ronnie Hill. Mary Adams Garner is not shown.
Faces in the above photo are obviously difficult to discern, so here are some zoomed-in photos of the participants.
Above are, from left to right: Johnny Craig, Danny Maness, Ricky Powell, Dennis McEachern, Jan Allen Segrest and Curtis Thompson.
Above are, from left to right: Curtis Thompson, Betty Carol Endsley Stanley, Penny Dreher Lyons, Linda Goodwin Elledge, Delores Maness Grimes, Jean Starling Burnett, John Bishop, Billy Bynum, Vicky Powell Paige, Bobby Works and Buddy Stevenson.
Above are, from left to right: Carroll Collier, Billy Bynum, Vicky Powell Paige, Bobby Works, Buddy Stevenson, Earl Vickers, Susie Cochran Hargis, Jimmy Ray Dickerson, Peggy Wilson Cook, and Ronnie Hill.
In the above photo of the middle group, one person is obscured, so here's another photo.
That's Barbara Price McGuffie behind Linda Goodwin Elledge and Jean Starling Burnett. Carroll Collier, Billy Bynum and John Bishop are obviously preoccupied with something besides the camera.
Three faculty members from the 1960's also attended the reunion.
From left to right: Coach Leo Johnson, Janiece Rogers Blount, and Jimmy Gray.
Class members who were unable to attend were Bobby Adams, Larry Adams, Tommy Harvey, Glenda Knott Givens, Rebecca Knott Fricks, Don McDonald and Bobby Earl Steed.
The Class of 1969 also paid tribute to the five deceased members of their class with a memory board of photographs. Those class members are Fred G. Berry, Jr. (1949–1992), Billy D. "Butch" Bland, Jr. (1951–2002), Fred H. Dreher III (1951–2008), Gary Dale Pickett (1951–1991) and Rose Hinds Thompson (1950–1996).
It's probably trite to say that a good time was had by all, but the class members seemed to me to genuinely enjoy each other's company.
On a personal note, I very much enjoyed visiting with Coach Leo Johnson, who is a veritable walking encyclopedia of happenings in the Bradley schools from the mid-1950's to the late 1960's. Two bits of trivia from our conversation:
Coach Johnson's paddle/strap was well known throughout the student body, both by students who had felt its sting and those who did not. Coach Johnson told me that any "paddle-able" offense, no matter how heinous, always drew a set number of "licks" (8).
Some of us remember watching Coach Johnson during games and thinking he was quite intense. In 17 years of coaching basketball (not all at Bradley), how many technical fouls did he get called for? (Answer: 3).
Summer is class reunion time and if any other classes which are reuniting will furnish a photo(s), or a short article on their affair, I'll be glad to post them.


Now under the helm of Claire Waight Keller, Givenchy's menswear continues to blend insouciant cool with the sophisticated heritage of the house. Expect minimalist sneakers and logo rubber pool slides.
SKU: EOX68.N8130. Categories: Flip Flops & Slides, Shoes. Tags: Givenchy, Mens, White.


Lately, I have been on the ride of my life. So much going on! Isn't a semester abroad supposed to be the "easiest" of all your semesters while in college?! I thought I was busy back in Chicago, but that does not compare to here a t all!I recently started my internship at the American Chamber of Commerce, located in Beijing! AmCham is basically a resource for companies from the United States (and beyond) to gain access to Chinese markets and business. They assist in all aspects crossing borders internationally. I work specifically under our Senior Director- John Zane. He is actually also on the board of directors at The Beijing Center as well…essentially he is my boss in every aspect of my life at TBC. He is the best! He challenges me at work and tells everything to me straight. My first day he gave me a stack of papers to examine and then told me that I would be writing a policy paper for him! That report would be sent to the American Embassy to be reviewed! That was nerve wracking because I was only used to writing papers andreports for class!
My latest work related event was a program that Amcham, the first in the series. It was called: Inter-Chamber Series- Career Women Forward. It was a joint task that consisted of the American Chamber, Australian Chamber, European Chamber, and many more. It is an initiative of dialogues from successful women from all around the world to share their story. Along with their awesome insight, they also spoke to the public about policies that they believe will promote gender diversity in the workplace. I got to visit the American Embassy here in Beijing and network with many people from all different industries. Although it is stressful, this internship has been the greatest opportunity I have had yet. It has taught me so much in so little time and I can finally say I have internationalized myself for my future career.


Try 50 free example AP World History test questions.
Aiming for a high score on your AP World History test? Look no further! Dynamic Path presents 150 review questions for College Board's World History Advanced Placement Exam.
This module contains professionally-written multiple-choice review questions. Each multiple-choice question is paired with a clear and thoughtful explanation and a detailed Key Takeaway that summarizes the main learning point of the question, time period, or figure discussed, ensuring a comprehensive understanding of the material. Learn at your own pace in Study Mode, or give yourself a timed quiz in Test Mode.
Questions cover topics in ancient world civilizations, such as the Shang, Sumarian, and Harrapan Civilizations, through the medieval, renaissance, and pre-modern period, and up to the Kyoto Protocol and modern political struggles.